completed big block refactoring in preparation for SET-BLOCK integration

23 files changed, 707 insertions, 541 deletions

diff --git a/src/block/Makefile.am b/src/block/Makefile.am
index 4a6d8e71e..da1d8257c 100644
--- a/src/block/Makefile.am
+++ b/src/block/Makefile.am
@@ -26,7 +26,7 @@ noinst_LTLIBRARIES = \
 libgnunet_plugin_block_template_la_SOURCES = \
   plugin_block_template.c
 libgnunet_plugin_block_template_la_LIBADD = \
-  libgnunetblock.la \
+  libgnunetblockgroup.la \
   $(top_builddir)/src/util/libgnunetutil.la \
   $(LTLIBINTL)
 libgnunet_plugin_block_template_la_LDFLAGS = \
@@ -35,8 +35,8 @@ libgnunet_plugin_block_template_la_LDFLAGS = \
 libgnunet_plugin_block_test_la_SOURCES = \
   plugin_block_test.c
 libgnunet_plugin_block_test_la_LIBADD = \
-  libgnunetblock.la \
-  $(top_builddir)/src/util/libgnunetutil.la  \
+  libgnunetblockgroup.la \
+$(top_builddir)/src/util/libgnunetutil.la  \
   $(LTLIBINTL)
 libgnunet_plugin_block_test_la_LDFLAGS = \
  $(GN_PLUGIN_LDFLAGS)
diff --git a/src/block/bg_bf.c b/src/block/bg_bf.c
index f03ae5247..9c4dc9060 100644
--- a/src/block/bg_bf.c
+++ b/src/block/bg_bf.c
@@ -56,6 +56,7 @@ struct BfGroupInternals
  * Serialize state of a block group.
  *
  * @param bg group to serialize
+ * @param[out] nonce set to the nonce of the @a bg
  * @param[out] raw_data set to the serialized state
  * @param[out] raw_data_size set to the number of bytes in @a raw_data
  * @return #GNUNET_OK on success, #GNUNET_NO if serialization is not
@@ -63,6 +64,7 @@ struct BfGroupInternals
  */
 static int
 bf_group_serialize_cb (struct GNUNET_BLOCK_Group *bg,
+                       uint32_t *nonce,
                        void **raw_data,
                        size_t *raw_data_size)
 {
@@ -78,6 +80,7 @@ bf_group_serialize_cb (struct GNUNET_BLOCK_Group *bg,
     GNUNET_break (0);
     return GNUNET_SYSERR;
   }
+  *nonce = gi->bf_mutator;
   *raw_data = raw;
   *raw_data_size = gi->bf_size;
   return GNUNET_OK;
@@ -85,6 +88,60 @@ bf_group_serialize_cb (struct GNUNET_BLOCK_Group *bg,
 
 
 /**
+ * Mark elements as "seen" using a hash of the element. Not supported
+ * by all block plugins.
+ *
+ * @param bg group to update
+ * @param seen_results results already seen
+ * @param seen_results_count number of entries in @a seen_results
+ */
+static void
+bf_group_mark_seen_cb (struct GNUNET_BLOCK_Group *bg,
+                       const struct GNUNET_HashCode *seen_results,
+                       unsigned int seen_results_count)
+{
+  struct BfGroupInternals *gi = bg->internal_cls;
+
+  for (unsigned int i=0;i<seen_results_count;i++)
+  {
+    struct GNUNET_HashCode mhash;
+
+    GNUNET_BLOCK_mingle_hash (&seen_results[i],
+                              gi->bf_mutator,
+                              &mhash);
+    GNUNET_CONTAINER_bloomfilter_add (gi->bf,
+                                      &mhash);
+  }
+}
+
+
+/**
+ * Merge two groups, if possible. Not supported by all block plugins,
+ * can also fail if the nonces were different.
+ *
+ * @param bg1 group to update
+ * @param bg2 group to merge into @a bg1
+ * @return #GNUNET_OK on success, #GNUNET_NO if the nonces were different and thus
+ *         we failed.
+ */
+static int
+bf_group_merge_cb (struct GNUNET_BLOCK_Group *bg1,
+                   const struct GNUNET_BLOCK_Group *bg2)
+{
+  struct BfGroupInternals *gi1 = bg1->internal_cls;
+  struct BfGroupInternals *gi2 = bg2->internal_cls;
+
+  if (gi1->bf_mutator != gi2->bf_mutator)
+    return GNUNET_NO;
+  if (gi1->bf_size != gi2->bf_size)
+    return GNUNET_NO;
+  GNUNET_CONTAINER_bloomfilter_or2 (gi1->bf,
+                                    gi2->bf);
+  return GNUNET_OK;
+}
+
+
+/**
  * Destroy resources used by a block group.
  *
  * @param bg group to destroy, NULL is allowed
@@ -134,6 +191,8 @@ GNUNET_BLOCK_GROUP_bf_create (void *cls,
   bg = GNUNET_new (struct GNUNET_BLOCK_Group);
   bg->type = type;
   bg->serialize_cb = &bf_group_serialize_cb;
+  bg->mark_seen_cb = &bf_group_mark_seen_cb;
+  bg->merge_cb = &bf_group_merge_cb;
   bg->destroy_cb = &bf_group_destroy_cb;
   bg->internal_cls = gi;
   return bg;
@@ -154,9 +213,12 @@ int
 GNUNET_BLOCK_GROUP_bf_test_and_set (struct GNUNET_BLOCK_Group *bg,
                                     const struct GNUNET_HashCode *hc)
 {
-  struct BfGroupInternals *gi = bg->internal_cls;
+  struct BfGroupInternals *gi;
   struct GNUNET_HashCode mhash;
 
+  if (NULL == bg)
+    return GNUNET_NO;
+  gi = bg->internal_cls;
   GNUNET_BLOCK_mingle_hash (hc,
                             gi->bf_mutator,
                             &mhash);
diff --git a/src/block/block.c b/src/block/block.c
index d4f5462dd..b7a19ae90 100644
--- a/src/block/block.c
+++ b/src/block/block.c
@@ -162,6 +162,7 @@ GNUNET_BLOCK_context_destroy (struct GNUNET_BLOCK_Context *ctx)
  * Serialize state of a block group.
  *
  * @param bg group to serialize
+ * @param[out] nonce set to the nonce of the @a bg
  * @param[out] raw_data set to the serialized state
  * @param[out] raw_data_size set to the number of bytes in @a raw_data
  * @return #GNUNET_OK on success, #GNUNET_NO if serialization is not
@@ -169,9 +170,11 @@ GNUNET_BLOCK_context_destroy (struct GNUNET_BLOCK_Context *ctx)
  */
 int
 GNUNET_BLOCK_group_serialize (struct GNUNET_BLOCK_Group *bg,
+                              uint32_t *nonce,
                               void **raw_data,
                               size_t *raw_data_size)
 {
+  *nonce = 0;
   *raw_data = NULL;
   *raw_data_size = 0;
   if (NULL == bg)
@@ -179,6 +182,7 @@ GNUNET_BLOCK_group_serialize (struct GNUNET_BLOCK_Group *bg,
   if (NULL == bg->serialize_cb)
     return GNUNET_NO;
   return bg->serialize_cb (bg,
+                           nonce,
                            raw_data,
                            raw_data_size);
 }
@@ -199,6 +203,41 @@ GNUNET_BLOCK_group_destroy (struct GNUNET_BLOCK_Group *bg)
 
 
 /**
+ * Try merging two block groups.  Afterwards, @a bg1 should remain
+ * valid and contain the rules from both @a bg1 and @bg2, and
+ * @a bg2 should be destroyed (as part of this call).  The latter
+ * should happen even if merging is not supported.
+ *
+ * @param[in,out] bg1 first group to merge, is updated
+ * @param bg2 second group to merge, is destroyed
+ * @return #GNUNET_OK on success,
+ *         #GNUNET_NO if merge failed due to different nonce
+ *         #GNUNET_SYSERR if merging is not supported
+ */
+int
+GNUNET_BLOCK_group_merge (struct GNUNET_BLOCK_Group *bg1,
+                          struct GNUNET_BLOCK_Group *bg2)
+{
+  int ret;
+
+  if (NULL == bg2)
+    return GNUNET_OK;
+  if (NULL == bg1)
+  {
+    bg2->destroy_cb (bg2);
+    return GNUNET_OK;
+  }
+  if (NULL == bg1->merge_cb)
+    return GNUNET_SYSERR;
+  GNUNET_assert (bg1->merge_cb == bg1->merge_cb);
+  ret = bg1->merge_cb (bg1,
+                       bg2);
+  bg2->destroy_cb (bg2);
+  return ret;
+}
+
+
+/**
  * Find a plugin for the given type.
  *
  * @param ctx context to search
@@ -244,19 +283,26 @@ GNUNET_BLOCK_group_create (struct GNUNET_BLOCK_Context *ctx,
                            enum GNUNET_BLOCK_Type type,
                            uint32_t nonce,
                            const void *raw_data,
-                           size_t raw_data_size)
+                           size_t raw_data_size,
+                           ...)
 {
   struct GNUNET_BLOCK_PluginFunctions *plugin;
+  struct GNUNET_BLOCK_Group *bg;
+  va_list ap;
 
   plugin = find_plugin (ctx,
                         type);
   if (NULL == plugin->create_group)
     return NULL;
-  return plugin->create_group (plugin->cls,
-                               type,
-                               nonce,
-                               raw_data,
-                               raw_data_size);
+  va_start (ap, raw_data_size);
+  bg = plugin->create_group (plugin->cls,
+                             type,
+                             nonce,
+                             raw_data,
+                             raw_data_size,
+                             ap);
+  va_end (ap);
+  return bg;
 }
 
 
@@ -269,10 +315,9 @@ GNUNET_BLOCK_group_create (struct GNUNET_BLOCK_Context *ctx,
  *
  * @param ctx block contxt
  * @param type block type
+ * @param block block group to use
  * @param eo control flags
  * @param query original query (hash)
- * @param bf pointer to bloom filter associated with query; possibly updated (!)
- * @param bf_mutator mutation value for @a bf
  * @param xquery extended query data (can be NULL, depending on type)
  * @param xquery_size number of bytes in @a xquery
  * @param reply_block response to validate
@@ -282,25 +327,24 @@ GNUNET_BLOCK_group_create (struct GNUNET_BLOCK_Context *ctx,
 enum GNUNET_BLOCK_EvaluationResult
 GNUNET_BLOCK_evaluate (struct GNUNET_BLOCK_Context *ctx,
                        enum GNUNET_BLOCK_Type type,
+                       struct GNUNET_BLOCK_Group *group,
                        enum GNUNET_BLOCK_EvaluationOptions eo,
                        const struct GNUNET_HashCode *query,
-                       struct GNUNET_CONTAINER_BloomFilter **bf,
-                       int32_t bf_mutator,
                        const void *xquery,
                        size_t xquery_size,
                        const void *reply_block,
                        size_t reply_block_size)
 {
-  struct GNUNET_BLOCK_PluginFunctions *plugin = find_plugin (ctx, type);
+  struct GNUNET_BLOCK_PluginFunctions *plugin = find_plugin (ctx,
+                                                             type);
 
-  if (plugin == NULL)
+  if (NULL == plugin)
     return GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED;
   return plugin->evaluate (plugin->cls,
                            type,
+                           group,
                            eo,
                            query,
-                           bf,
-                           bf_mutator,
                            xquery,
                            xquery_size,
                            reply_block,
@@ -326,7 +370,8 @@ GNUNET_BLOCK_get_key (struct GNUNET_BLOCK_Context *ctx,
                       size_t block_size,
                       struct GNUNET_HashCode *key)
 {
-  struct GNUNET_BLOCK_PluginFunctions *plugin = find_plugin (ctx, type);
+  struct GNUNET_BLOCK_PluginFunctions *plugin = find_plugin (ctx,
+                                                             type);
 
   if (plugin == NULL)
     return GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED;
@@ -335,65 +380,29 @@ GNUNET_BLOCK_get_key (struct GNUNET_BLOCK_Context *ctx,
 
 
 /**
- * How many bytes should a bloomfilter be if we have already seen
- * entry_count responses?  Note that #GNUNET_CONSTANTS_BLOOMFILTER_K
- * gives us the number of bits set per entry.  Furthermore, we should
- * not re-size the filter too often (to keep it cheap).
- *
- * Since other peers will also add entries but not resize the filter,
- * we should generally pick a slightly larger size than what the
- * strict math would suggest.
- *
- * @param entry_count expected number of entries in the Bloom filter
- * @return must be a power of two and smaller or equal to 2^15.
- */
-static size_t
-compute_bloomfilter_size (unsigned int entry_count)
-{
-  size_t size;
-  unsigned int ideal = (entry_count * GNUNET_CONSTANTS_BLOOMFILTER_K) / 4;
-  uint16_t max = 1 << 15;
-
-  if (entry_count > max)
-    return max;
-  size = 8;
-  while ((size < max) && (size < ideal))
-    size *= 2;
-  if (size > max)
-    return max;
-  return size;
-}
-
-
-/**
- * Construct a bloom filter that would filter out the given
- * results.
+ * Update block group to filter out the given results.  Note that the
+ * use of a hash for seen results implies that the caller magically
+ * knows how the specific block engine hashes for filtering
+ * duplicates, so this API may not always apply.
  *
  * @param bf_mutator mutation value to use
  * @param seen_results results already seen
  * @param seen_results_count number of entries in @a seen_results
- * @return NULL if seen_results_count is 0, otherwise a BF
- *         that would match the given results.
+ * @return #GNUNET_SYSERR if not supported, #GNUNET_OK on success
  */
-struct GNUNET_CONTAINER_BloomFilter *
-GNUNET_BLOCK_construct_bloomfilter (int32_t bf_mutator,
-                                    const struct GNUNET_HashCode *seen_results,
-                                    unsigned int seen_results_count)
+int
+GNUNET_BLOCK_group_set_seen (struct GNUNET_BLOCK_Group *bg,
+                             const struct GNUNET_HashCode *seen_results,
+                             unsigned int seen_results_count)
 {
-  struct GNUNET_CONTAINER_BloomFilter *bf;
-  struct GNUNET_HashCode mhash;
-  unsigned int i;
-  size_t nsize;
-
-  nsize = compute_bloomfilter_size (seen_results_count);
-  bf = GNUNET_CONTAINER_bloomfilter_init (NULL, nsize,
-                                          GNUNET_CONSTANTS_BLOOMFILTER_K);
-  for (i = 0; i < seen_results_count; i++)
-  {
-    GNUNET_BLOCK_mingle_hash (&seen_results[i], bf_mutator, &mhash);
-    GNUNET_CONTAINER_bloomfilter_add (bf, &mhash);
-  }
-  return bf;
+  if (NULL == bg)
+    return GNUNET_OK;
+  if (NULL == bg->mark_seen_cb)
+    return GNUNET_SYSERR;
+  bg->mark_seen_cb (bg,
+                    seen_results,
+                    seen_results_count);
+  return GNUNET_OK;
 }
 
 
diff --git a/src/block/plugin_block_template.c b/src/block/plugin_block_template.c
index 6cb69ef5f..0e8107af2 100644
--- a/src/block/plugin_block_template.c
+++ b/src/block/plugin_block_template.c
@@ -26,9 +26,52 @@
 
 #include "platform.h"
 #include "gnunet_block_plugin.h"
+#include "gnunet_block_group_lib.h"
 
 #define DEBUG_TEMPLATE GNUNET_EXTRA_LOGGING
 
+/**
+ * Number of bits we set per entry in the bloomfilter.
+ * Do not change!
+ */
+#define BLOOMFILTER_K 16
+
+
+/**
+ * How big is the BF we use for DHT blocks?
+ */
+#define TEMPLATE_BF_SIZE 8
+
+
+/**
+ * Create a new block group.
+ *
+ * @param ctx block context in which the block group is created
+ * @param type type of the block for which we are creating the group
+ * @param nonce random value used to seed the group creation
+ * @param raw_data optional serialized prior state of the group, NULL if unavailable/fresh
+ * @param raw_data_size number of bytes in @a raw_data, 0 if unavailable/fresh
+ * @param va variable arguments specific to @a type
+ * @return block group handle, NULL if block groups are not supported
+ *         by this @a type of block (this is not an error)
+ */
+static struct GNUNET_BLOCK_Group *
+block_plugin_template_create_group (void *cls,
+                                    enum GNUNET_BLOCK_Type type,
+                                    uint32_t nonce,
+                                    const void *raw_data,
+                                    size_t raw_data_size,
+                                    va_list va)
+{
+  return GNUNET_BLOCK_GROUP_bf_create (cls,
+                                       TEMPLATE_BF_SIZE,
+                                       BLOOMFILTER_K,
+                                       type,
+                                       nonce,
+                                       raw_data,
+                                       raw_data_size);
+}
+
 
 /**
  * Function called to validate a reply or a request.  For
@@ -36,10 +79,9 @@
  *
  * @param cls closure
  * @param type block type
+ * @param group block group to use
  * @param eo control flags
  * @param query original query (hash)
- * @param bf pointer to bloom filter associated with query; possibly updated (!)
- * @param bf_mutator mutation value for bf
  * @param xquery extrended query data (can be NULL, depending on type)
  * @param xquery_size number of bytes in xquery
  * @param reply_block response to validate
@@ -49,36 +91,25 @@
 static enum GNUNET_BLOCK_EvaluationResult
 block_plugin_template_evaluate (void *cls,
                                 enum GNUNET_BLOCK_Type type,
+                                struct GNUNET_BLOCK_Group *group,
                                 enum GNUNET_BLOCK_EvaluationOptions eo,
                                 const struct GNUNET_HashCode *query,
-                                struct GNUNET_CONTAINER_BloomFilter **bf,
-                                int32_t bf_mutator,
                                 const void *xquery,
                                 size_t xquery_size,
                                 const void *reply_block,
                                 size_t reply_block_size)
 {
   struct GNUNET_HashCode chash;
-  struct GNUNET_HashCode mhash;
-  /* FIXME: check validity first... */
 
-  /* mandatory duplicate-detection code... */
-  if (NULL != bf)
-  {
-    GNUNET_CRYPTO_hash (reply_block, reply_block_size, &chash);
-    GNUNET_BLOCK_mingle_hash (&chash, bf_mutator, &mhash);
-    if (NULL != *bf)
-    {
-      if (GNUNET_YES == GNUNET_CONTAINER_bloomfilter_test (*bf, &mhash))
-        return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
-    }
-    else
-    {
-      *bf = GNUNET_CONTAINER_bloomfilter_init (NULL, 8, 64 /* BLOOMFILTER_K */);
-    }
-    GNUNET_CONTAINER_bloomfilter_add (*bf, &mhash);
-  }
-  /* FIXME: other stuff here... */
+  if (NULL == reply_block)
+    return GNUNET_BLOCK_EVALUATION_REQUEST_VALID;
+  GNUNET_CRYPTO_hash (reply_block,
+                      reply_block_size,
+                      &chash);
+  if (GNUNET_YES ==
+      GNUNET_BLOCK_GROUP_bf_test_and_set (group,
+                                          &chash))
+    return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
   return GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED;
 }
 
@@ -91,13 +122,15 @@ block_plugin_template_evaluate (void *cls,
  * @param block block to get the key for
  * @param block_size number of bytes in block
  * @param key set to the key (query) for the given block
- * @return GNUNET_OK on success, GNUNET_SYSERR if type not supported
+ * @return #GNUNET_OK on success, #GNUNET_SYSERR if type not supported
  *         (or if extracting a key from a block of this type does not work)
  */
 static int
-block_plugin_template_get_key (void *cls, enum GNUNET_BLOCK_Type type,
-                               const void *block, size_t block_size,
-                               struct GNUNET_HashCode * key)
+block_plugin_template_get_key (void *cls,
+                               enum GNUNET_BLOCK_Type type,
+                               const void *block,
+                               size_t block_size,
+                               struct GNUNET_HashCode *key)
 {
   return GNUNET_SYSERR;
 }
@@ -119,6 +152,7 @@ libgnunet_plugin_block_template_init (void *cls)
   api = GNUNET_new (struct GNUNET_BLOCK_PluginFunctions);
   api->evaluate = &block_plugin_template_evaluate;
   api->get_key = &block_plugin_template_get_key;
+  api->create_group = &block_plugin_template_create_group;
   api->types = types;
   return api;
 }
diff --git a/src/block/plugin_block_test.c b/src/block/plugin_block_test.c
index b692d6230..615f1571b 100644
--- a/src/block/plugin_block_test.c
+++ b/src/block/plugin_block_test.c
@@ -27,7 +27,7 @@
 
 #include "platform.h"
 #include "gnunet_block_plugin.h"
-
+#include "gnunet_block_group_lib.h"
 
 /**
  * Number of bits we set per entry in the bloomfilter.
@@ -36,15 +36,50 @@
 #define BLOOMFILTER_K 16
 
 /**
+ * How big is the BF we use for DHT blocks?
+ */
+#define TEST_BF_SIZE 8
+
+
+/**
+ * Create a new block group.
+ *
+ * @param ctx block context in which the block group is created
+ * @param type type of the block for which we are creating the group
+ * @param nonce random value used to seed the group creation
+ * @param raw_data optional serialized prior state of the group, NULL if unavailable/fresh
+ * @param raw_data_size number of bytes in @a raw_data, 0 if unavailable/fresh
+ * @param va variable arguments specific to @a type
+ * @return block group handle, NULL if block groups are not supported
+ *         by this @a type of block (this is not an error)
+ */
+static struct GNUNET_BLOCK_Group *
+block_plugin_test_create_group (void *cls,
+                                enum GNUNET_BLOCK_Type type,
+                                uint32_t nonce,
+                                const void *raw_data,
+                                size_t raw_data_size,
+                                va_list va)
+{
+  return GNUNET_BLOCK_GROUP_bf_create (cls,
+                                       TEST_BF_SIZE,
+                                       BLOOMFILTER_K,
+                                       type,
+                                       nonce,
+                                       raw_data,
+                                       raw_data_size);
+}
+
+
+/**
  * Function called to validate a reply or a request.  For
  * request evaluation, simply pass "NULL" for the reply_block.
  *
  * @param cls closure
  * @param type block type
+ * @param group group to check against
  * @param eo control flags
  * @param query original query (hash)
- * @param bf pointer to bloom filter associated with query; possibly updated (!)
- * @param bf_mutator mutation value for @a bf
  * @param xquery extrended query data (can be NULL, depending on type)
  * @param xquery_size number of bytes in @a xquery
  * @param reply_block response to validate
@@ -54,20 +89,21 @@
 static enum GNUNET_BLOCK_EvaluationResult
 block_plugin_test_evaluate (void *cls,
                             enum GNUNET_BLOCK_Type type,
+                            struct GNUNET_BLOCK_Group *group,
                             enum GNUNET_BLOCK_EvaluationOptions eo,
                             const struct GNUNET_HashCode *query,
-                            struct GNUNET_CONTAINER_BloomFilter **bf,
-                            int32_t bf_mutator,
                             const void *xquery,
                             size_t xquery_size,
                             const void *reply_block,
                             size_t reply_block_size)
 {
   struct GNUNET_HashCode chash;
-  struct GNUNET_HashCode mhash;
 
   if ( GNUNET_BLOCK_TYPE_TEST != type)
+  {
+    GNUNET_break (0);
     return GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED;
+  }
   if (0 != xquery_size)
   {
     GNUNET_break_op (0);
@@ -75,22 +111,13 @@ block_plugin_test_evaluate (void *cls,
   }
   if (NULL == reply_block)
     return GNUNET_BLOCK_EVALUATION_REQUEST_VALID;
-
-  if (NULL != bf)
-  {
-    GNUNET_CRYPTO_hash (reply_block, reply_block_size, &chash);
-    GNUNET_BLOCK_mingle_hash (&chash, bf_mutator, &mhash);
-    if (NULL != *bf)
-    {
-      if (GNUNET_YES == GNUNET_CONTAINER_bloomfilter_test (*bf, &mhash))
-        return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
-    }
-    else
-    {
-      *bf = GNUNET_CONTAINER_bloomfilter_init (NULL, 8, BLOOMFILTER_K);
-    }
-    GNUNET_CONTAINER_bloomfilter_add (*bf, &mhash);
-  }
+  GNUNET_CRYPTO_hash (reply_block,
+                      reply_block_size,
+                      &chash);
+  if (GNUNET_YES ==
+      GNUNET_BLOCK_GROUP_bf_test_and_set (group,
+                                          &chash))
+    return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
   return GNUNET_BLOCK_EVALUATION_OK_MORE;
 }
 
@@ -107,9 +134,11 @@ block_plugin_test_evaluate (void *cls,
  *         (or if extracting a key from a block of this type does not work)
  */
 static int
-block_plugin_test_get_key (void *cls, enum GNUNET_BLOCK_Type type,
-                           const void *block, size_t block_size,
-                           struct GNUNET_HashCode * key)
+block_plugin_test_get_key (void *cls,
+                           enum GNUNET_BLOCK_Type type,
+                           const void *block,
+                           size_t block_size,
+                           struct GNUNET_HashCode *key)
 {
   /* always fails since there is no fixed relationship between
    * keys and values for test values */
@@ -136,6 +165,7 @@ libgnunet_plugin_block_test_init (void *cls)
   api = GNUNET_new (struct GNUNET_BLOCK_PluginFunctions);
   api->evaluate = &block_plugin_test_evaluate;
   api->get_key = &block_plugin_test_get_key;
+  api->create_group = &block_plugin_test_create_group;
   api->types = types;
   return api;
 }
diff --git a/src/dht/Makefile.am b/src/dht/Makefile.am
index 93dae9f6e..4216af400 100644
--- a/src/dht/Makefile.am
+++ b/src/dht/Makefile.am
@@ -82,6 +82,7 @@ gnunet_service_dht_LDADD = \
   $(top_builddir)/src/peerinfo/libgnunetpeerinfo.la \
   $(top_builddir)/src/hello/libgnunethello.la \
   $(top_builddir)/src/block/libgnunetblock.la \
+  $(top_builddir)/src/block/libgnunetblockgroup.la \
   $(top_builddir)/src/datacache/libgnunetdatacache.la \
   $(top_builddir)/src/util/libgnunetutil.la \
   -lm
@@ -102,6 +103,7 @@ gnunet_service_dht_xvine_LDADD = \
   $(top_builddir)/src/peerinfo/libgnunetpeerinfo.la \
   $(top_builddir)/src/hello/libgnunethello.la \
   $(top_builddir)/src/block/libgnunetblock.la \
+  $(top_builddir)/src/block/libgnunetblockgroup.la \
   $(top_builddir)/src/datacache/libgnunetdatacache.la \
   $(top_builddir)/src/util/libgnunetutil.la \
   -lm
@@ -120,6 +122,7 @@ gnunet_service_dht_whanau_LDADD = \
   $(top_builddir)/src/peerinfo/libgnunetpeerinfo.la \
   $(top_builddir)/src/hello/libgnunethello.la \
   $(top_builddir)/src/block/libgnunetblock.la \
+  $(top_builddir)/src/block/libgnunetblockgroup.la \
   $(top_builddir)/src/datacache/libgnunetdatacache.la \
   $(top_builddir)/src/util/libgnunetutil.la \
   -lm
diff --git a/src/dht/gnunet-service-dht_clients.c b/src/dht/gnunet-service-dht_clients.c
index 5ba4e5820..a42356e5f 100644
--- a/src/dht/gnunet-service-dht_clients.c
+++ b/src/dht/gnunet-service-dht_clients.c
@@ -1,6 +1,6 @@
 /*
      This file is part of GNUnet.
-     Copyright (C) 2009, 2010, 2011, 2016 GNUnet e.V.
+     Copyright (C) 2009, 2010, 2011, 2016, 2017 GNUnet e.V.
 
      GNUnet is free software; you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published
@@ -362,21 +362,22 @@ client_disconnect_cb (void *cls,
 static void
 transmit_request (struct ClientQueryRecord *cqr)
 {
-  int32_t reply_bf_mutator;
-  struct GNUNET_CONTAINER_BloomFilter *reply_bf;
+  struct GNUNET_BLOCK_Group *bg;
   struct GNUNET_CONTAINER_BloomFilter *peer_bf;
 
   GNUNET_STATISTICS_update (GDS_stats,
                             gettext_noop ("# GET requests from clients injected"),
                             1,
                             GNUNET_NO);
-  reply_bf_mutator =
-      (int32_t) GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
-                                          UINT32_MAX);
-  reply_bf
-    = GNUNET_BLOCK_construct_bloomfilter (reply_bf_mutator,
-                                          cqr->seen_replies,
-                                          cqr->seen_replies_count);
+  bg = GNUNET_BLOCK_group_create (GDS_block_context,
+                                  cqr->type,
+                                  GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
+                                                            UINT32_MAX),
+                                  NULL,
+                                  0);
+  GNUNET_BLOCK_group_set_seen (bg,
+                               cqr->seen_replies,
+                               cqr->seen_replies_count);
   peer_bf
     = GNUNET_CONTAINER_bloomfilter_init (NULL,
                                          DHT_BLOOM_SIZE,
@@ -393,10 +394,9 @@ transmit_request (struct ClientQueryRecord *cqr)
                              &cqr->key,
                              cqr->xquery,
                              cqr->xquery_size,
-                             reply_bf,
-                             reply_bf_mutator,
+                             bg,
                              peer_bf);
-  GNUNET_CONTAINER_bloomfilter_free (reply_bf);
+  GNUNET_BLOCK_group_destroy (bg);
   GNUNET_CONTAINER_bloomfilter_free (peer_bf);
 
   /* exponential back-off for retries.
@@ -668,7 +668,6 @@ handle_dht_local_get (void *cls,
                             cqr->xquery,
                             xquery_size,
                             NULL,
-                            0,
                             &handle_local_result,
                             ch);
   GNUNET_SERVICE_client_continue (ch->client);
@@ -1052,10 +1051,9 @@ forward_reply (void *cls,
   eval
     = GNUNET_BLOCK_evaluate (GDS_block_context,
                              record->type,
+                             NULL,
                              GNUNET_BLOCK_EO_NONE,
                              key,
-                             NULL,
-                             0,
                              record->xquery,
                              record->xquery_size,
                              frc->data,
diff --git a/src/dht/gnunet-service-dht_datacache.c b/src/dht/gnunet-service-dht_datacache.c
index 74fa1cc29..fef637cad 100644
--- a/src/dht/gnunet-service-dht_datacache.c
+++ b/src/dht/gnunet-service-dht_datacache.c
@@ -1,6 +1,6 @@
 /*
      This file is part of GNUnet.
-     Copyright (C) 2009, 2010, 2011, 2015 GNUnet e.V.
+     Copyright (C) 2009, 2010, 2011, 2015, 2017 GNUnet e.V.
 
      GNUnet is free software; you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published
@@ -109,39 +109,34 @@ struct GetRequestContext
   const void *xquery;
 
   /**
-   * Bloomfilter to filter out duplicate replies (updated)
-   */
-  struct GNUNET_CONTAINER_BloomFilter **reply_bf;
-
-  /**
    * The key this request was about
    */
   struct GNUNET_HashCode key;
 
   /**
-   * Number of bytes in xquery.
+   * Block group to use to evaluate replies (updated)
    */
-  size_t xquery_size;
+  struct GNUNET_BLOCK_Group *bg;
 
   /**
-   * Mutator value for the @e reply_bf, see gnunet_block_lib.h
+   * Function to call on results.
    */
-  uint32_t reply_bf_mutator;
+  GDS_DATACACHE_GetCallback gc;
 
   /**
-   * Return value to give back.
+   * Closure for @e gc.
    */
-  enum GNUNET_BLOCK_EvaluationResult eval;
+  void *gc_cls;
 
   /**
-   * Function to call on results.
+   * Number of bytes in xquery.
    */
-  GDS_DATACACHE_GetCallback gc;
+  size_t xquery_size;
 
   /**
-   * Closure for @e gc.
+   * Return value to give back.
    */
-  void *gc_cls;
+  enum GNUNET_BLOCK_EvaluationResult eval;
 
 };
 
@@ -181,10 +176,9 @@ datacache_get_iterator (void *cls,
   eval
     = GNUNET_BLOCK_evaluate (GDS_block_context,
                              type,
+                             ctx->bg,
                              GNUNET_BLOCK_EO_LOCAL_SKIP_CRYPTO,
                              key,
-                             ctx->reply_bf,
-                             ctx->reply_bf_mutator,
                              ctx->xquery,
                              ctx->xquery_size,
                              data,
@@ -256,8 +250,7 @@ datacache_get_iterator (void *cls,
  * @param type requested data type
  * @param xquery extended query
  * @param xquery_size number of bytes in @a xquery
- * @param reply_bf where the reply bf is (to be) stored, possibly updated, can be NULL
- * @param reply_bf_mutator mutation value for @a reply_bf
+ * @param bg block group to use for reply evaluation
  * @param gc function to call on the results
  * @param gc_cls closure for @a gc
  * @return evaluation result for the local replies
@@ -267,8 +260,7 @@ GDS_DATACACHE_handle_get (const struct GNUNET_HashCode *key,
                           enum GNUNET_BLOCK_Type type,
                           const void *xquery,
                           size_t xquery_size,
-                          struct GNUNET_CONTAINER_BloomFilter **reply_bf,
-                          uint32_t reply_bf_mutator,
+                          struct GNUNET_BLOCK_Group *bg,
                           GDS_DATACACHE_GetCallback gc,
                           void *gc_cls)
 {
@@ -285,8 +277,7 @@ GDS_DATACACHE_handle_get (const struct GNUNET_HashCode *key,
   ctx.key = *key;
   ctx.xquery = xquery;
   ctx.xquery_size = xquery_size;
-  ctx.reply_bf = reply_bf;
-  ctx.reply_bf_mutator = reply_bf_mutator;
+  ctx.bg = bg;
   ctx.gc = gc;
   ctx.gc_cls = gc_cls;
   r = GNUNET_DATACACHE_get (datacache,
diff --git a/src/dht/gnunet-service-dht_datacache.h b/src/dht/gnunet-service-dht_datacache.h
index 5069883c7..ff6ae23da 100644
--- a/src/dht/gnunet-service-dht_datacache.h
+++ b/src/dht/gnunet-service-dht_datacache.h
@@ -87,8 +87,7 @@ typedef void
  * @param type requested data type
  * @param xquery extended query
  * @param xquery_size number of bytes in xquery
- * @param reply_bf where the reply bf is (to be) stored, possibly updated!, can be NULL
- * @param reply_bf_mutator mutation value for reply_bf
+ * @param bg block group to use for evaluation of replies
  * @param gc function to call on the results
  * @param gc_cls closure for @a gc
  * @return evaluation result for the local replies
@@ -98,8 +97,7 @@ GDS_DATACACHE_handle_get (const struct GNUNET_HashCode *key,
                           enum GNUNET_BLOCK_Type type,
                           const void *xquery,
                           size_t xquery_size,
-                          struct GNUNET_CONTAINER_BloomFilter **reply_bf,
-                          uint32_t reply_bf_mutator,
+                          struct GNUNET_BLOCK_Group *bg,
                           GDS_DATACACHE_GetCallback gc,
                           void *gc_cls);
 
diff --git a/src/dht/gnunet-service-dht_neighbours.c b/src/dht/gnunet-service-dht_neighbours.c
index 7f3a44588..1bbc95a06 100644
--- a/src/dht/gnunet-service-dht_neighbours.c
+++ b/src/dht/gnunet-service-dht_neighbours.c
@@ -1,6 +1,6 @@
 /*
      This file is part of GNUnet.
-     Copyright (C) 2009-2016 GNUnet e.V.
+     Copyright (C) 2009-2017 GNUnet e.V.
 
      GNUnet is free software; you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published
@@ -27,6 +27,7 @@
 #include "platform.h"
 #include "gnunet_util_lib.h"
 #include "gnunet_block_lib.h"
+#include "gnunet_block_group_lib.h"
 #include "gnunet_hello_lib.h"
 #include "gnunet_constants.h"
 #include "gnunet_protocols.h"
@@ -50,7 +51,7 @@
 
 /**
  * Enable slow sanity checks to debug issues.
- */ 
+ */
 #define SANITY_CHECKS 1
 
 /**
@@ -602,27 +603,10 @@ update_connect_preferences ()
 
 
 /**
- * Closure for #add_known_to_bloom().
- */
-struct BloomConstructorContext
-{
-  /**
-   * Bloom filter under construction.
-   */
-  struct GNUNET_CONTAINER_BloomFilter *bloom;
-
-  /**
-   * Mutator to use.
-   */
-  uint32_t bf_mutator;
-};
-
-
-/**
  * Add each of the peers we already know to the bloom filter of
  * the request so that we don't get duplicate HELLOs.
  *
- * @param cls the 'struct BloomConstructorContext'.
+ * @param cls the `struct GNUNET_BLOCK_Group`
  * @param key peer identity to add to the bloom filter
  * @param value value the peer information (unused)
  * @return #GNUNET_YES (we should continue to iterate)
@@ -632,22 +616,17 @@ add_known_to_bloom (void *cls,
                     const struct GNUNET_PeerIdentity *key,
                     void *value)
 {
-  struct BloomConstructorContext *ctx = cls;
+  struct GNUNET_BLOCK_Group *bg = cls;
   struct GNUNET_HashCode key_hash;
-  struct GNUNET_HashCode mh;
 
   GNUNET_CRYPTO_hash (key,
                       sizeof (struct GNUNET_PeerIdentity),
                       &key_hash);
-  GNUNET_BLOCK_mingle_hash (&key_hash,
-                            ctx->bf_mutator,
-                            &mh);
+  GNUNET_BLOCK_GROUP_bf_test_and_set (bg,
+                                      &key_hash);
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
-              "Adding known peer (%s) to bloomfilter for FIND PEER with mutation %u\n",
-              GNUNET_i2s (key),
-              ctx->bf_mutator);
-  GNUNET_CONTAINER_bloomfilter_add (ctx->bloom,
-                                    &mh);
+              "Adding known peer (%s) to bloomfilter for FIND PEER\n",
+              GNUNET_i2s (key));
   return GNUNET_YES;
 }
 
@@ -663,7 +642,7 @@ static void
 send_find_peer_message (void *cls)
 {
   struct GNUNET_TIME_Relative next_send_time;
-  struct BloomConstructorContext bcc;
+  struct GNUNET_BLOCK_Group *bg;
   struct GNUNET_CONTAINER_BloomFilter *peer_bf;
 
   find_peer_task = NULL;
@@ -677,30 +656,37 @@ send_find_peer_message (void *cls)
     newly_found_peers = 0;
     return;
   }
-  bcc.bf_mutator =
-      GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
-                                UINT32_MAX);
-  bcc.bloom =
-      GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE,
-                                         GNUNET_CONSTANTS_BLOOMFILTER_K);
+  bg = GNUNET_BLOCK_GROUP_bf_create (NULL,
+                                     DHT_BLOOM_SIZE,
+                                     GNUNET_CONSTANTS_BLOOMFILTER_K,
+                                     GNUNET_BLOCK_TYPE_DHT_HELLO,
+                                     GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
+                                                               UINT32_MAX),
+                                     NULL,
+                                     0);
   GNUNET_CONTAINER_multipeermap_iterate (all_connected_peers,
                                          &add_known_to_bloom,
-                                         &bcc);
+                                         bg);
   GNUNET_STATISTICS_update (GDS_stats,
                             gettext_noop ("# FIND PEER messages initiated"),
                             1,
                             GNUNET_NO);
-  peer_bf =
-      GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE,
+  peer_bf
+    = GNUNET_CONTAINER_bloomfilter_init (NULL,
+                                         DHT_BLOOM_SIZE,
                                          GNUNET_CONSTANTS_BLOOMFILTER_K);
   // FIXME: pass priority!?
   GDS_NEIGHBOURS_handle_get (GNUNET_BLOCK_TYPE_DHT_HELLO,
                              GNUNET_DHT_RO_FIND_PEER,
-                             FIND_PEER_REPLICATION_LEVEL, 0,
-                             &my_identity_hash, NULL, 0, bcc.bloom,
-                             bcc.bf_mutator, peer_bf);
+                             FIND_PEER_REPLICATION_LEVEL,
+                             0,
+                             &my_identity_hash,
+                             NULL,
+                             0,
+                             bg,
+                             peer_bf);
   GNUNET_CONTAINER_bloomfilter_free (peer_bf);
-  GNUNET_CONTAINER_bloomfilter_free (bcc.bloom);
+  GNUNET_BLOCK_group_destroy (bg);
   /* schedule next round */
   next_send_time.rel_value_us =
       DHT_MINIMUM_FIND_PEER_INTERVAL.rel_value_us +
@@ -1357,8 +1343,7 @@ GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
  * @param key key for the content
  * @param xquery extended query
  * @param xquery_size number of bytes in @a xquery
- * @param reply_bf bloomfilter to filter duplicates
- * @param reply_bf_mutator mutator for @a reply_bf
+ * @param bg group to use for filtering replies
  * @param peer_bf filter for peers not to select (again)
  * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
  */
@@ -1366,14 +1351,14 @@ int
 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
                            enum GNUNET_DHT_RouteOption options,
                            uint32_t desired_replication_level,
-                           uint32_t hop_count, const struct GNUNET_HashCode * key,
-                           const void *xquery, size_t xquery_size,
-                           const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
-                           uint32_t reply_bf_mutator,
+                           uint32_t hop_count,
+                           const struct GNUNET_HashCode *key,
+                           const void *xquery,
+                           size_t xquery_size,
+                           struct GNUNET_BLOCK_Group *bg,
                            struct GNUNET_CONTAINER_BloomFilter *peer_bf)
 {
   unsigned int target_count;
-  unsigned int i;
   struct PeerInfo **targets;
   struct PeerInfo *target;
   struct GNUNET_MQ_Envelope *env;
@@ -1381,7 +1366,9 @@ GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
   struct PeerGetMessage *pgm;
   char *xq;
   size_t reply_bf_size;
+  void *reply_bf;
   unsigned int skip_count;
+  uint32_t bf_nonce;
 
   GNUNET_assert (NULL != peer_bf);
   GNUNET_STATISTICS_update (GDS_stats,
@@ -1408,11 +1395,22 @@ GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
                 GNUNET_i2s (&my_identity));
     return GNUNET_NO;
   }
-  reply_bf_size = GNUNET_CONTAINER_bloomfilter_get_size (reply_bf);
+  if (GNUNET_OK !=
+      GNUNET_BLOCK_group_serialize (bg,
+                                    &bf_nonce,
+                                    &reply_bf,
+                                    &reply_bf_size))
+  {
+    reply_bf = NULL;
+    reply_bf_size = 0;
+    bf_nonce = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
+                                         UINT32_MAX);
+  }
   msize = xquery_size + reply_bf_size;
   if (msize + sizeof (struct PeerGetMessage) >= GNUNET_SERVER_MAX_MESSAGE_SIZE)
   {
     GNUNET_break (0);
+    GNUNET_free_non_null (reply_bf);
     GNUNET_free (targets);
     return GNUNET_NO;
   }
@@ -1422,7 +1420,7 @@ GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
                             GNUNET_NO);
   /* forward request */
   skip_count = 0;
-  for (i = 0; i < target_count; i++)
+  for (unsigned int i = 0; i < target_count; i++)
   {
     target = targets[i];
     if (GNUNET_MQ_get_length (target->mq) >= MAXIMUM_PENDING_PER_PEER)
@@ -1447,7 +1445,7 @@ GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
     pgm->hop_count = htonl (hop_count + 1);
     pgm->desired_replication_level = htonl (desired_replication_level);
     pgm->xquery_size = htonl (xquery_size);
-    pgm->bf_mutator = reply_bf_mutator;
+    pgm->bf_mutator = bf_nonce;
     GNUNET_break (GNUNET_YES ==
                   GNUNET_CONTAINER_bloomfilter_test (peer_bf,
                                                      &target->phash));
@@ -1460,16 +1458,14 @@ GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
     GNUNET_memcpy (xq,
                    xquery,
                    xquery_size);
-    if (NULL != reply_bf)
-      GNUNET_assert (GNUNET_OK ==
-                     GNUNET_CONTAINER_bloomfilter_get_raw_data (reply_bf,
-                                                                &xq
-                                                                [xquery_size],
-                                                                reply_bf_size));
+    GNUNET_memcpy (&xq[xquery_size],
+                   reply_bf,
+                   reply_bf_size);
     GNUNET_MQ_send (target->mq,
                     env);
   }
   GNUNET_free (targets);
+  GNUNET_free_non_null (reply_bf);
   return (skip_count < target_count) ? GNUNET_OK : GNUNET_NO;
 }
 
@@ -1717,11 +1713,12 @@ handle_dht_p2p_put (void *cls,
   {
     switch (GNUNET_BLOCK_evaluate (GDS_block_context,
                                    ntohl (put->type),
+                                   NULL, /* query group */
                                    GNUNET_BLOCK_EO_NONE,
                                    NULL,    /* query */
-                                   NULL, 0, /* bloom filer */
                                    NULL, 0, /* xquery */
-                                   payload, payload_size))
+                                   payload,
+                                   payload_size))
     {
     case GNUNET_BLOCK_EVALUATION_OK_MORE:
     case GNUNET_BLOCK_EVALUATION_OK_LAST:
@@ -1762,7 +1759,7 @@ handle_dht_p2p_put (void *cls,
         }
         GNUNET_break (0 != memcmp (&pp[i],
                                    peer->id,
-                                   sizeof (struct GNUNET_PeerIdentity)));       
+                                   sizeof (struct GNUNET_PeerIdentity)));
       }
 #endif
       GNUNET_memcpy (pp,
@@ -1830,30 +1827,25 @@ handle_dht_p2p_put (void *cls,
  *
  * @param sender sender of the FIND PEER request
  * @param key peers close to this key are desired
- * @param bf peers matching this bf are excluded
- * @param bf_mutator mutator for bf
+ * @param bg group for filtering peers
  */
 static void
 handle_find_peer (const struct GNUNET_PeerIdentity *sender,
                   const struct GNUNET_HashCode *key,
-                  struct GNUNET_CONTAINER_BloomFilter *bf,
-                  uint32_t bf_mutator)
+                  struct GNUNET_BLOCK_Group *bg)
 {
   int bucket_idx;
   struct PeerBucket *bucket;
   struct PeerInfo *peer;
   unsigned int choice;
-  struct GNUNET_HashCode mhash;
   const struct GNUNET_HELLO_Message *hello;
 
   /* first, check about our own HELLO */
   if (NULL != GDS_my_hello)
   {
-    GNUNET_BLOCK_mingle_hash (&my_identity_hash,
-                              bf_mutator,
-                              &mhash);
-    if ((NULL == bf) ||
-        (GNUNET_YES != GNUNET_CONTAINER_bloomfilter_test (bf, &mhash)))
+    if (GNUNET_YES !=
+        GNUNET_BLOCK_GROUP_bf_test_and_set (bg,
+                                            &my_identity_hash))
     {
       size_t hello_size;
 
@@ -1913,18 +1905,15 @@ handle_find_peer (const struct GNUNET_PeerIdentity *sender,
   do
   {
     peer = peer->next;
-    if (choice-- == 0)
+    if (0 == choice--)
       return;                   /* no non-masked peer available */
     if (NULL == peer)
       peer = bucket->head;
-    GNUNET_BLOCK_mingle_hash (&peer->phash,
-                              bf_mutator,
-                              &mhash);
     hello = GDS_HELLO_get (peer->id);
-  } while ( (hello == NULL) ||
-            (GNUNET_YES ==
-             GNUNET_CONTAINER_bloomfilter_test (bf,
-                                                &mhash)) );
+  } while ( (NULL == hello) ||
+            (GNUNET_YES ==
+             GNUNET_BLOCK_GROUP_bf_test_and_set (bg,
+                                                 &peer->phash)) );
   GDS_NEIGHBOURS_handle_reply (sender,
                                GNUNET_BLOCK_TYPE_DHT_HELLO,
                                GNUNET_TIME_relative_to_absolute
@@ -2019,7 +2008,7 @@ handle_dht_p2p_get (void *cls,
   enum GNUNET_BLOCK_Type type;
   enum GNUNET_DHT_RouteOption options;
   enum GNUNET_BLOCK_EvaluationResult eval;
-  struct GNUNET_CONTAINER_BloomFilter *reply_bf;
+  struct GNUNET_BLOCK_Group *bg;
   struct GNUNET_CONTAINER_BloomFilter *peer_bf;
   const char *xquery;
   int forwarded;
@@ -2036,7 +2025,6 @@ handle_dht_p2p_get (void *cls,
   type = ntohl (get->type);
   options = ntohl (get->options);
   xquery = (const char *) &get[1];
-  reply_bf = NULL;
   GNUNET_STATISTICS_update (GDS_stats,
                             gettext_noop ("# P2P GET requests received"),
                             1,
@@ -2064,19 +2052,17 @@ handle_dht_p2p_get (void *cls,
                  xquery);
     GNUNET_free (tmp);
   }
-
-  if (reply_bf_size > 0)
-    reply_bf =
-        GNUNET_CONTAINER_bloomfilter_init (&xquery[xquery_size],
-                                           reply_bf_size,
-                                           GNUNET_CONSTANTS_BLOOMFILTER_K);
-  eval =
-      GNUNET_BLOCK_evaluate (GDS_block_context,
+  bg = GNUNET_BLOCK_group_create (GDS_block_context,
+                                  type,
+                                  get->bf_mutator,
+                                  &xquery[xquery_size],
+                                  reply_bf_size);
+  eval
+    = GNUNET_BLOCK_evaluate (GDS_block_context,
                              type,
+                             bg,
                              GNUNET_BLOCK_EO_NONE,
                              &get->key,
-                             &reply_bf,
-                             get->bf_mutator,
                              xquery,
                              xquery_size,
                              NULL,
@@ -2085,8 +2071,7 @@ handle_dht_p2p_get (void *cls,
   {
     /* request invalid or block type not supported */
     GNUNET_break_op (eval == GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED);
-    if (NULL != reply_bf)
-      GNUNET_CONTAINER_bloomfilter_free (reply_bf);
+    GNUNET_BLOCK_group_destroy (bg);
     return;
   }
   peer_bf = GNUNET_CONTAINER_bloomfilter_init (get->bloomfilter,
@@ -2098,12 +2083,11 @@ handle_dht_p2p_get (void *cls,
   /* remember request for routing replies */
   GDS_ROUTING_add (peer->id,
                    type,
+                   bg, /* bg now owned by routing, but valid at least until end of this function! */
                    options,
                    &get->key,
                    xquery,
-                   xquery_size,
-                   reply_bf,
-                   get->bf_mutator);
+                   xquery_size);
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
               "GET for %s at %s after %u hops\n",
               GNUNET_h2s (&get->key),
@@ -2122,8 +2106,7 @@ handle_dht_p2p_get (void *cls,
                                 GNUNET_NO);
       handle_find_peer (peer->id,
                         &get->key,
-                        reply_bf,
-                        get->bf_mutator);
+                        bg);
     }
     else
     {
@@ -2131,8 +2114,7 @@ handle_dht_p2p_get (void *cls,
                                        type,
                                        xquery,
                                        xquery_size,
-                                       &reply_bf,
-                                       get->bf_mutator,
+                                       bg,
                                        &handle_local_result,
                                        NULL);
     }
@@ -2155,8 +2137,7 @@ handle_dht_p2p_get (void *cls,
                                            &get->key,
                                            xquery,
                                            xquery_size,
-                                           reply_bf,
-                                           get->bf_mutator,
+                                           bg,
                                            peer_bf);
   GDS_CLIENTS_process_get (options
                            | (GNUNET_OK == forwarded)
@@ -2168,10 +2149,7 @@ handle_dht_p2p_get (void *cls,
                            NULL,
                            &get->key);
 
-
-  /* clean up */
-  if (NULL != reply_bf)
-    GNUNET_CONTAINER_bloomfilter_free (reply_bf);
+  /* clean up; note that 'bg' is owned by routing now! */
   GNUNET_CONTAINER_bloomfilter_free (peer_bf);
 }
 
@@ -2310,7 +2288,7 @@ handle_dht_p2p_result (void *cls,
       }
       GNUNET_break (0 != memcmp (&get_path[i],
                                  peer->id,
-                                 sizeof (struct GNUNET_PeerIdentity))); 
+                                 sizeof (struct GNUNET_PeerIdentity)));
     }
 #endif
     GNUNET_memcpy (xget_path,
diff --git a/src/dht/gnunet-service-dht_neighbours.h b/src/dht/gnunet-service-dht_neighbours.h
index d89e5c54f..34b76ee8a 100644
--- a/src/dht/gnunet-service-dht_neighbours.h
+++ b/src/dht/gnunet-service-dht_neighbours.h
@@ -77,8 +77,7 @@ GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
  * @param key key for the content
  * @param xquery extended query
  * @param xquery_size number of bytes in @a xquery
- * @param reply_bf bloomfilter to filter duplicates
- * @param reply_bf_mutator mutator for @a reply_bf
+ * @param bg block group to filter replies
  * @param peer_bf filter for peers not to select (again, updated)
  * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
  */
@@ -88,9 +87,9 @@ GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
                            uint32_t desired_replication_level,
                            uint32_t hop_count,
                            const struct GNUNET_HashCode *key,
-                           const void *xquery, size_t xquery_size,
-                           const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
-                           uint32_t reply_bf_mutator,
+                           const void *xquery,
+                           size_t xquery_size,
+                           struct GNUNET_BLOCK_Group *bg,
                            struct GNUNET_CONTAINER_BloomFilter *peer_bf);
 
 
@@ -114,12 +113,13 @@ void
 GDS_NEIGHBOURS_handle_reply (const struct GNUNET_PeerIdentity *target,
                              enum GNUNET_BLOCK_Type type,
                              struct GNUNET_TIME_Absolute expiration_time,
-                             const struct GNUNET_HashCode * key,
+                             const struct GNUNET_HashCode *key,
                              unsigned int put_path_length,
                              const struct GNUNET_PeerIdentity *put_path,
                              unsigned int get_path_length,
                              const struct GNUNET_PeerIdentity *get_path,
-                             const void *data, size_t data_size);
+                             const void *data,
+                             size_t data_size);
 
 
 /**
diff --git a/src/dht/gnunet-service-dht_routing.c b/src/dht/gnunet-service-dht_routing.c
index 71240a503..252995737 100644
--- a/src/dht/gnunet-service-dht_routing.c
+++ b/src/dht/gnunet-service-dht_routing.c
@@ -58,9 +58,9 @@ struct RecentRequest
   struct GNUNET_CONTAINER_HeapNode *heap_node;
 
   /**
-   * Bloomfilter for replies to drop.
+   * Block group for filtering replies.
    */
-  struct GNUNET_CONTAINER_BloomFilter *reply_bf;
+  struct GNUNET_BLOCK_Group *bg;
 
   /**
    * Type of the requested block.
@@ -79,11 +79,6 @@ struct RecentRequest
   size_t xquery_size;
 
   /**
-   * Mutator value for the reply_bf, see gnunet_block_lib.h
-   */
-  uint32_t reply_bf_mutator;
-
-  /**
    * Request options.
    */
   enum GNUNET_DHT_RouteOption options;
@@ -207,10 +202,9 @@ process (void *cls,
   eval
     = GNUNET_BLOCK_evaluate (GDS_block_context,
                              pc->type,
+                             rr->bg,
                              GNUNET_BLOCK_EO_NONE,
                              eval_key,
-                             &rr->reply_bf,
-                             rr->reply_bf_mutator,
                              rr->xquery,
                              rr->xquery_size,
                              pc->data,
@@ -343,7 +337,7 @@ expire_oldest_entry ()
   recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
   GNUNET_assert (recent_req != NULL);
   GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node);
-  GNUNET_CONTAINER_bloomfilter_free (recent_req->reply_bf);
+  GNUNET_BLOCK_group_destroy (recent_req->bg);
   GNUNET_assert (GNUNET_YES ==
                  GNUNET_CONTAINER_multihashmap_remove (recent_map,
                                                        &recent_req->key,
@@ -379,18 +373,10 @@ try_combine_recent (void *cls,
                      rr->xquery,
                      in->xquery_size)) )
     return GNUNET_OK;
-  if (in->reply_bf_mutator != rr->reply_bf_mutator)
-  {
-    rr->reply_bf_mutator = in->reply_bf_mutator;
-    GNUNET_CONTAINER_bloomfilter_free (rr->reply_bf);
-    rr->reply_bf = in->reply_bf;
-  }
-  else
-  {
-    GNUNET_CONTAINER_bloomfilter_or2 (rr->reply_bf,
-                                      in->reply_bf);
-    GNUNET_CONTAINER_bloomfilter_free (in->reply_bf);
-  }
+  GNUNET_break (GNUNET_SYSERR !=
+                GNUNET_BLOCK_group_merge (in->bg,
+                                          rr->bg));
+  rr->bg = in->bg;
   GNUNET_free (in);
   return GNUNET_SYSERR;
 }
@@ -411,12 +397,11 @@ try_combine_recent (void *cls,
 void
 GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender,
                  enum GNUNET_BLOCK_Type type,
+                 struct GNUNET_BLOCK_Group *bg,
                  enum GNUNET_DHT_RouteOption options,
                  const struct GNUNET_HashCode *key,
                  const void *xquery,
-                 size_t xquery_size,
-                 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
-                 uint32_t reply_bf_mutator)
+                 size_t xquery_size)
 {
   struct RecentRequest *recent_req;
 
@@ -424,17 +409,19 @@ GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender,
     expire_oldest_entry ();
   GNUNET_STATISTICS_update (GDS_stats,
                             gettext_noop ("# Entries added to routing table"),
-                            1, GNUNET_NO);
+                            1,
+                            GNUNET_NO);
   recent_req = GNUNET_malloc (sizeof (struct RecentRequest) + xquery_size);
   recent_req->peer = *sender;
   recent_req->key = *key;
-  recent_req->reply_bf = GNUNET_CONTAINER_bloomfilter_copy (reply_bf);
+  recent_req->bg = bg;
   recent_req->type = type;
   recent_req->options = options;
   recent_req->xquery = &recent_req[1];
-  GNUNET_memcpy (&recent_req[1], xquery, xquery_size);
+  GNUNET_memcpy (&recent_req[1],
+                 xquery,
+                 xquery_size);
   recent_req->xquery_size = xquery_size;
-  recent_req->reply_bf_mutator = reply_bf_mutator;
   if (GNUNET_SYSERR ==
       GNUNET_CONTAINER_multihashmap_get_multiple (recent_map,
                                                   key,
@@ -447,13 +434,14 @@ GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender,
                               1, GNUNET_NO);
     return;
   }
-  recent_req->heap_node =
-      GNUNET_CONTAINER_heap_insert (recent_heap, recent_req,
+  recent_req->heap_node
+    = GNUNET_CONTAINER_heap_insert (recent_heap,
+                                    recent_req,
                                     GNUNET_TIME_absolute_get ().abs_value_us);
-  GNUNET_CONTAINER_multihashmap_put (recent_map, key, recent_req,
+  GNUNET_CONTAINER_multihashmap_put (recent_map,
+                                     key,
+                                     recent_req,
                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
-
-
 }
 
 
diff --git a/src/dht/gnunet-service-dht_routing.h b/src/dht/gnunet-service-dht_routing.h
index 7c57361dc..1d9284164 100644
--- a/src/dht/gnunet-service-dht_routing.h
+++ b/src/dht/gnunet-service-dht_routing.h
@@ -67,21 +67,20 @@ GDS_ROUTING_process (void *cls,
  *
  * @param sender peer that originated the request
  * @param type type of the block
+ * @param bg block group to evaluate replies, henceforth owned by routing
  * @param options options for processing
  * @param key key for the content
  * @param xquery extended query
  * @param xquery_size number of bytes in @a xquery
- * @param reply_bf bloomfilter to filter duplicates
- * @param reply_bf_mutator mutator for @a reply_bf
 */
 void
 GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender,
                  enum GNUNET_BLOCK_Type type,
+                 struct GNUNET_BLOCK_Group *bg,
                  enum GNUNET_DHT_RouteOption options,
-                 const struct GNUNET_HashCode * key, const void *xquery,
-                 size_t xquery_size,
-                 const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
-                 uint32_t reply_bf_mutator);
+                 const struct GNUNET_HashCode * key,
+                 const void *xquery,
+                 size_t xquery_size);
 
 
 /**
diff --git a/src/dht/plugin_block_dht.c b/src/dht/plugin_block_dht.c
index 4c5f122a4..0304dad87 100644
--- a/src/dht/plugin_block_dht.c
+++ b/src/dht/plugin_block_dht.c
@@ -47,6 +47,7 @@
  * @param nonce random value used to seed the group creation
  * @param raw_data optional serialized prior state of the group, NULL if unavailable/fresh
  * @param raw_data_size number of bytes in @a raw_data, 0 if unavailable/fresh
+ * @param va variable arguments specific to @a type
  * @return block group handle, NULL if block groups are not supported
  *         by this @a type of block (this is not an error)
  */
@@ -55,7 +56,8 @@ block_plugin_dht_create_group (void *cls,
                                enum GNUNET_BLOCK_Type type,
                                uint32_t nonce,
                                const void *raw_data,
-                               size_t raw_data_size)
+                               size_t raw_data_size,
+                               va_list va)
 {
   return GNUNET_BLOCK_GROUP_bf_create (cls,
                                        DHT_BF_SIZE,
@@ -73,10 +75,9 @@ block_plugin_dht_create_group (void *cls,
  *
  * @param cls closure
  * @param type block type
+ * @param group block group to check against
  * @param eo control flags
  * @param query original query (hash)
- * @param bf pointer to bloom filter associated with query; possibly updated (!)
- * @param bf_mutator mutation value for @a bf
  * @param xquery extended query data (can be NULL, depending on type)
  * @param xquery_size number of bytes in @a xquery
  * @param reply_block response to validate
@@ -86,16 +87,14 @@ block_plugin_dht_create_group (void *cls,
 static enum GNUNET_BLOCK_EvaluationResult
 block_plugin_dht_evaluate (void *cls,
                            enum GNUNET_BLOCK_Type type,
+                           struct GNUNET_BLOCK_Group *group,
                            enum GNUNET_BLOCK_EvaluationOptions eo,
                            const struct GNUNET_HashCode *query,
-                           struct GNUNET_CONTAINER_BloomFilter **bf,
-                           int32_t bf_mutator,
                            const void *xquery,
                            size_t xquery_size,
                            const void *reply_block,
                            size_t reply_block_size)
 {
-  struct GNUNET_HashCode mhash;
   const struct GNUNET_HELLO_Message *hello;
   struct GNUNET_PeerIdentity pid;
   const struct GNUNET_MessageHeader *msg;
@@ -127,22 +126,13 @@ block_plugin_dht_evaluate (void *cls,
     GNUNET_break_op (0);
     return GNUNET_BLOCK_EVALUATION_RESULT_INVALID;
   }
-  if (NULL != bf)
-  {
-    GNUNET_CRYPTO_hash (&pid, sizeof (pid), &phash);
-    GNUNET_BLOCK_mingle_hash (&phash, bf_mutator, &mhash);
-    if (NULL != *bf)
-    {
-      if (GNUNET_YES == GNUNET_CONTAINER_bloomfilter_test (*bf, &mhash))
-        return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
-    }
-    else
-    {
-      *bf = GNUNET_CONTAINER_bloomfilter_init (NULL, 8,
-                                               GNUNET_CONSTANTS_BLOOMFILTER_K);
-    }
-    GNUNET_CONTAINER_bloomfilter_add (*bf, &mhash);
-  }
+  GNUNET_CRYPTO_hash (&pid,
+                      sizeof (pid),
+                      &phash);
+  if (GNUNET_YES ==
+      GNUNET_BLOCK_GROUP_bf_test_and_set (group,
+                                          &phash))
+    return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
   return GNUNET_BLOCK_EVALUATION_OK_MORE;
 }
 
diff --git a/src/dns/plugin_block_dns.c b/src/dns/plugin_block_dns.c
index e4bc9209c..65da0de63 100644
--- a/src/dns/plugin_block_dns.c
+++ b/src/dns/plugin_block_dns.c
@@ -39,10 +39,9 @@
  *
  * @param cls closure
  * @param type block type
+ * @param bg group to evaluate against
  * @param eo control flags
  * @param query original query (hash)
- * @param bf pointer to bloom filter associated with query; possibly updated (!)
- * @param bf_mutator mutation value for bf
  * @param xquery extended query data (can be NULL, depending on type)
  * @param xquery_size number of bytes in @a xquery
  * @param reply_block response to validate
@@ -52,10 +51,9 @@
 static enum GNUNET_BLOCK_EvaluationResult
 block_plugin_dns_evaluate (void *cls,
                            enum GNUNET_BLOCK_Type type,
+                           struct GNUNET_BLOCK_Group *bg,
                            enum GNUNET_BLOCK_EvaluationOptions eo,
                            const struct GNUNET_HashCode * query,
-                           struct GNUNET_CONTAINER_BloomFilter **bf,
-                           int32_t bf_mutator,
                            const void *xquery,
                            size_t xquery_size,
                            const void *reply_block,
diff --git a/src/fs/gnunet-service-fs_pr.c b/src/fs/gnunet-service-fs_pr.c
index 63462f7dc..87e2d2ee1 100644
--- a/src/fs/gnunet-service-fs_pr.c
+++ b/src/fs/gnunet-service-fs_pr.c
@@ -97,9 +97,9 @@ struct GSF_PendingRequest
   struct GNUNET_HashCode *replies_seen;
 
   /**
-   * Bloomfilter masking replies we've already seen.
+   * Block group for filtering replies we've already seen.
    */
-  struct GNUNET_CONTAINER_BloomFilter *bf;
+  struct GNUNET_BLOCK_Group *bg;
 
   /**
    * Entry for this pending request in the expiration heap, or NULL.
@@ -190,11 +190,6 @@ struct GSF_PendingRequest
   unsigned int replies_seen_size;
 
   /**
-   * Mingle value we currently use for the bf.
-   */
-  uint32_t mingle;
-
-  /**
    * Do we have a first UID yet?
    */
   unsigned int have_first_uid;
@@ -248,18 +243,35 @@ static unsigned long long max_pending_requests = (32 * 1024);
  * fresh one of minimal size without problems) OR if our peer is the
  * initiator (in which case we may resize to larger than mimimum size).
  *
+ * @param type type of the request
  * @param pr request for which the BF is to be recomputed
  */
 static void
-refresh_bloomfilter (struct GSF_PendingRequest *pr)
+refresh_bloomfilter (enum GNUNET_BLOCK_Type type,
+                     struct GSF_PendingRequest *pr)
 {
-  if (pr->bf != NULL)
-    GNUNET_CONTAINER_bloomfilter_free (pr->bf);
-  pr->mingle =
-      GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX);
-  pr->bf =
-      GNUNET_BLOCK_construct_bloomfilter (pr->mingle, pr->replies_seen,
-                                          pr->replies_seen_count);
+  if (NULL != pr->bg)
+  {
+    GNUNET_BLOCK_group_destroy (pr->bg);
+    pr->bg = NULL;
+  }
+  if (GNUNET_BLOCK_TYPE_FS_UBLOCK != type)
+    return; /* no need */
+  pr->bg
+    = GNUNET_BLOCK_group_create (GSF_block_ctx,
+                                 type,
+                                 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
+                                                           UINT32_MAX),
+                                 NULL,
+                                 0,
+                                 "fs-seen-set-size",
+                                 pr->replies_seen_count);
+  if (NULL == pr->bg)
+    return;
+  GNUNET_break (GNUNET_OK ==
+                GNUNET_BLOCK_group_set_seen (pr->bg,
+                                             pr->replies_seen,
+                                             pr->replies_seen_count));
 }
 
 
@@ -355,25 +367,30 @@ GSF_pending_request_create_ (enum GSF_PendingRequestOptions options,
   if (replies_seen_count > 0)
   {
     pr->replies_seen_size = replies_seen_count;
-    pr->replies_seen =
-        GNUNET_malloc (sizeof (struct GNUNET_HashCode) * pr->replies_seen_size);
+    pr->replies_seen = GNUNET_new_array (pr->replies_seen_size,
+                                         struct GNUNET_HashCode);
     GNUNET_memcpy (pr->replies_seen,
-            replies_seen,
-            replies_seen_count * sizeof (struct GNUNET_HashCode));
+                   replies_seen,
+                   replies_seen_count * sizeof (struct GNUNET_HashCode));
     pr->replies_seen_count = replies_seen_count;
   }
-  if (NULL != bf_data)
+  if ( (NULL != bf_data) &&
+       (GNUNET_BLOCK_TYPE_FS_UBLOCK == pr->public_data.type) )
   {
-    pr->bf =
-        GNUNET_CONTAINER_bloomfilter_init (bf_data,
-                                           bf_size,
-                                           GNUNET_CONSTANTS_BLOOMFILTER_K);
-    pr->mingle = mingle;
+    pr->bg
+      =  GNUNET_BLOCK_group_create (GSF_block_ctx,
+                                    pr->public_data.type,
+                                    mingle,
+                                    bf_data,
+                                    bf_size,
+                                    "fs-seen-set-size",
+                                    0);
   }
   else if ((replies_seen_count > 0) &&
            (0 != (options & GSF_PRO_BLOOMFILTER_FULL_REFRESH)))
   {
-    refresh_bloomfilter (pr);
+    refresh_bloomfilter (pr->public_data.type,
+                         pr);
   }
   GNUNET_CONTAINER_multihashmap_put (pr_map,
                                      &pr->public_data.query,
@@ -461,46 +478,37 @@ GSF_pending_request_update_ (struct GSF_PendingRequest *pr,
                              const struct GNUNET_HashCode * replies_seen,
                              unsigned int replies_seen_count)
 {
-  unsigned int i;
-  struct GNUNET_HashCode mhash;
-
   if (replies_seen_count + pr->replies_seen_count < pr->replies_seen_count)
     return;                     /* integer overflow */
   if (0 != (pr->public_data.options & GSF_PRO_BLOOMFILTER_FULL_REFRESH))
   {
     /* we're responsible for the BF, full refresh */
     if (replies_seen_count + pr->replies_seen_count > pr->replies_seen_size)
-      GNUNET_array_grow (pr->replies_seen, pr->replies_seen_size,
+      GNUNET_array_grow (pr->replies_seen,
+                         pr->replies_seen_size,
                          replies_seen_count + pr->replies_seen_count);
-    GNUNET_memcpy (&pr->replies_seen[pr->replies_seen_count], replies_seen,
-            sizeof (struct GNUNET_HashCode) * replies_seen_count);
+    GNUNET_memcpy (&pr->replies_seen[pr->replies_seen_count],
+                   replies_seen,
+                   sizeof (struct GNUNET_HashCode) * replies_seen_count);
     pr->replies_seen_count += replies_seen_count;
-    refresh_bloomfilter (pr);
+    refresh_bloomfilter (pr->public_data.type,
+                         pr);
   }
   else
   {
-    if (NULL == pr->bf)
+    if (NULL == pr->bg)
     {
       /* we're not the initiator, but the initiator did not give us
        * any bloom-filter, so we need to create one on-the-fly */
-      pr->mingle =
-          GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
-                                    UINT32_MAX);
-      pr->bf =
-          GNUNET_BLOCK_construct_bloomfilter (pr->mingle,
-                                              replies_seen,
-                                              replies_seen_count);
+      refresh_bloomfilter (pr->public_data.type,
+                           pr);
     }
     else
     {
-      for (i = 0; i < pr->replies_seen_count; i++)
-      {
-        GNUNET_BLOCK_mingle_hash (&replies_seen[i],
-                                  pr->mingle,
-                                  &mhash);
-        GNUNET_CONTAINER_bloomfilter_add (pr->bf,
-                                          &mhash);
-      }
+      GNUNET_break (GNUNET_OK ==
+                    GNUNET_BLOCK_group_set_seen (pr->bg,
+                                                 replies_seen,
+                                                 pr->replies_seen_count));
     }
   }
   if (NULL != pr->gh)
@@ -530,6 +538,8 @@ GSF_pending_request_get_message_ (struct GSF_PendingRequest *pr)
   struct GNUNET_TIME_Absolute now;
   int64_t ttl;
   int do_route;
+  void *bf_data;
+  uint32_t bf_nonce;
 
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
               "Building request message for `%s' of type %d\n",
@@ -553,7 +563,15 @@ GSF_pending_request_get_message_ (struct GSF_PendingRequest *pr)
     bm |= GET_MESSAGE_BIT_TRANSMIT_TO;
     k++;
   }
-  bf_size = GNUNET_CONTAINER_bloomfilter_get_size (pr->bf);
+  if (GNUNET_OK !=
+      GNUNET_BLOCK_group_serialize (pr->bg,
+                                    &bf_nonce,
+                                    &bf_data,
+                                    &bf_size))
+  {
+    bf_size = 0;
+    bf_data = NULL;
+  }
   env = GNUNET_MQ_msg_extra (gm,
                              bf_size + k * sizeof (struct GNUNET_PeerIdentity),
                              GNUNET_MESSAGE_TYPE_FS_GET);
@@ -571,7 +589,7 @@ GSF_pending_request_get_message_ (struct GSF_PendingRequest *pr)
   now = GNUNET_TIME_absolute_get ();
   ttl = (int64_t) (pr->public_data.ttl.abs_value_us - now.abs_value_us);
   gm->ttl = htonl (ttl / 1000LL / 1000LL);
-  gm->filter_mutator = htonl (pr->mingle);
+  gm->filter_mutator = htonl (bf_nonce);
   gm->hash_bitmap = htonl (bm);
   gm->query = pr->public_data.query;
   ext = (struct GNUNET_PeerIdentity *) &gm[1];
@@ -581,11 +599,10 @@ GSF_pending_request_get_message_ (struct GSF_PendingRequest *pr)
                          &ext[k++]);
   if (NULL != pr->public_data.target)
     ext[k++] = *pr->public_data.target;
-  if (NULL != pr->bf)
-    GNUNET_assert (GNUNET_SYSERR !=
-                   GNUNET_CONTAINER_bloomfilter_get_raw_data (pr->bf,
-                                                              (char *) &ext[k],
-                                                              bf_size));
+  GNUNET_memcpy (&ext[k],
+                 bf_data,
+                 bf_size);
+  GNUNET_free_non_null (bf_data);
   return env;
 }
 
@@ -624,11 +641,8 @@ clean_request (void *cls,
   }
   GSF_plan_notify_request_done_ (pr);
   GNUNET_free_non_null (pr->replies_seen);
-  if (NULL != pr->bf)
-  {
-    GNUNET_CONTAINER_bloomfilter_free (pr->bf);
-    pr->bf = NULL;
-  }
+  GNUNET_BLOCK_group_destroy (pr->bg);
+  pr->bg = NULL;
   GNUNET_PEER_change_rc (pr->sender_pid, -1);
   pr->sender_pid = 0;
   GNUNET_PEER_change_rc (pr->origin_pid, -1);
@@ -844,10 +858,9 @@ process_reply (void *cls,
   prq->eval =
       GNUNET_BLOCK_evaluate (GSF_block_ctx,
                              prq->type,
+                             pr->bg,
                              prq->eo,
                              key,
-                             &pr->bf,
-                             pr->mingle,
                              NULL,
                              0,
                              prq->data,
diff --git a/src/fs/plugin_block_fs.c b/src/fs/plugin_block_fs.c
index 038734082..6c574fca2 100644
--- a/src/fs/plugin_block_fs.c
+++ b/src/fs/plugin_block_fs.c
@@ -28,6 +28,7 @@
 #include "gnunet_fs_service.h"
 #include "block_fs.h"
 #include "gnunet_signatures.h"
+#include "gnunet_constants.h"
 #include "gnunet_block_group_lib.h"
 
 
@@ -37,10 +38,36 @@
  */
 #define BLOOMFILTER_K 16
 
+
 /**
- * How big is the BF we use for FS blocks?
+ * How many bytes should a bloomfilter be if we have already seen
+ * entry_count responses?  Note that #GNUNET_CONSTANTS_BLOOMFILTER_K
+ * gives us the number of bits set per entry.  Furthermore, we should
+ * not re-size the filter too often (to keep it cheap).
+ *
+ * Since other peers will also add entries but not resize the filter,
+ * we should generally pick a slightly larger size than what the
+ * strict math would suggest.
+ *
+ * @param entry_count expected number of entries in the Bloom filter
+ * @return must be a power of two and smaller or equal to 2^15.
  */
-#define FS_BF_SIZE 8
+static size_t
+compute_bloomfilter_size (unsigned int entry_count)
+{
+  size_t size;
+  unsigned int ideal = (entry_count * GNUNET_CONSTANTS_BLOOMFILTER_K) / 4;
+  uint16_t max = 1 << 15;
+
+  if (entry_count > max)
+    return max;
+  size = 8;
+  while ((size < max) && (size < ideal))
+    size *= 2;
+  if (size > max)
+    return max;
+  return size;
+}
 
 
 /**
@@ -51,16 +78,21 @@
  * @param nonce random value used to seed the group creation
  * @param raw_data optional serialized prior state of the group, NULL if unavailable/fresh
  * @param raw_data_size number of bytes in @a raw_data, 0 if unavailable/fresh
+ * @param va variable arguments specific to @a type
  * @return block group handle, NULL if block groups are not supported
  *         by this @a type of block (this is not an error)
  */
 static struct GNUNET_BLOCK_Group *
 block_plugin_fs_create_group (void *cls,
-                               enum GNUNET_BLOCK_Type type,
-                               uint32_t nonce,
-                               const void *raw_data,
-                               size_t raw_data_size)
+                              enum GNUNET_BLOCK_Type type,
+                              uint32_t nonce,
+                              const void *raw_data,
+                              size_t raw_data_size,
+                              va_list va)
 {
+  unsigned int size;
+  const char *guard;
+
   switch (type)
   {
   case GNUNET_BLOCK_TYPE_FS_DBLOCK:
@@ -68,8 +100,23 @@ block_plugin_fs_create_group (void *cls,
   case GNUNET_BLOCK_TYPE_FS_IBLOCK:
     return NULL;
   case GNUNET_BLOCK_TYPE_FS_UBLOCK:
+    guard = va_arg (va, const char *);
+    if (0 != memcmp (guard,
+                     "fs-seen-set-size",
+                     strlen ("fs-seen-set-size")))
+    {
+      /* va-args invalid! bad bug, complain! */
+      GNUNET_break (0);
+      size = 8;
+    }
+    else
+    {
+      size = compute_bloomfilter_size (va_arg (va, unsigned int));
+    }
+    if (0 == size)
+      size = raw_data_size; /* not for us to determine, use what we got! */
     return GNUNET_BLOCK_GROUP_bf_create (cls,
-                                         FS_BF_SIZE,
+                                         size,
                                          BLOOMFILTER_K,
                                          type,
                                          nonce,
@@ -91,10 +138,9 @@ block_plugin_fs_create_group (void *cls,
  *
  * @param cls closure
  * @param type block type
+ * @param bg group to use for evaluation
  * @param eo control flags
  * @param query original query (hash)
- * @param bf pointer to bloom filter associated with query; possibly updated (!)
- * @param bf_mutator mutation value for @a bf
  * @param xquery extrended query data (can be NULL, depending on type)
  * @param xquery_size number of bytes in @a xquery
  * @param reply_block response to validate
@@ -104,10 +150,9 @@ block_plugin_fs_create_group (void *cls,
 static enum GNUNET_BLOCK_EvaluationResult
 block_plugin_fs_evaluate (void *cls,
                           enum GNUNET_BLOCK_Type type,
+                          struct GNUNET_BLOCK_Group *bg,
                           enum GNUNET_BLOCK_EvaluationOptions eo,
                           const struct GNUNET_HashCode *query,
-                          struct GNUNET_CONTAINER_BloomFilter **bf,
-                          int32_t bf_mutator,
                           const void *xquery,
                           size_t xquery_size,
                           const void *reply_block,
@@ -116,7 +161,6 @@ block_plugin_fs_evaluate (void *cls,
   const struct UBlock *ub;
   struct GNUNET_HashCode hc;
   struct GNUNET_HashCode chash;
-  struct GNUNET_HashCode mhash;
 
   switch (type)
   {
@@ -170,26 +214,13 @@ block_plugin_fs_evaluate (void *cls,
       GNUNET_break_op (0);
       return GNUNET_BLOCK_EVALUATION_RESULT_INVALID;
     }
-    if (NULL != bf)
-    {
-      GNUNET_CRYPTO_hash (reply_block,
-                          reply_block_size,
-                          &chash);
-      GNUNET_BLOCK_mingle_hash (&chash,
-                                bf_mutator,
-                                &mhash);
-      if (NULL != *bf)
-      {
-        if (GNUNET_YES ==
-            GNUNET_CONTAINER_bloomfilter_test (*bf, &mhash))
-          return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
-      }
-      else
-      {
-        *bf = GNUNET_CONTAINER_bloomfilter_init (NULL, 8, BLOOMFILTER_K);
-      }
-      GNUNET_CONTAINER_bloomfilter_add (*bf, &mhash);
-    }
+    GNUNET_CRYPTO_hash (reply_block,
+                        reply_block_size,
+                        &chash);
+    if (GNUNET_YES ==
+        GNUNET_BLOCK_GROUP_bf_test_and_set (bg,
+                                            &chash))
+      return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
     return GNUNET_BLOCK_EVALUATION_OK_MORE;
   default:
     return GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED;
diff --git a/src/fs/test_plugin_block_fs.c b/src/fs/test_plugin_block_fs.c
index 1fc9f2110..ba4f28bc5 100644
--- a/src/fs/test_plugin_block_fs.c
+++ b/src/fs/test_plugin_block_fs.c
@@ -40,28 +40,28 @@ test_fs (struct GNUNET_BLOCK_Context *ctx)
   if (GNUNET_BLOCK_EVALUATION_OK_LAST !=
       GNUNET_BLOCK_evaluate (ctx,
                              GNUNET_BLOCK_TYPE_FS_DBLOCK,
+                             NULL,
                              GNUNET_BLOCK_EO_NONE,
                              &key,
                              NULL, 0,
-                             NULL, 0,
                              block, sizeof (block)))
     return 2;
   if (GNUNET_BLOCK_EVALUATION_REQUEST_VALID !=
       GNUNET_BLOCK_evaluate (ctx,
                              GNUNET_BLOCK_TYPE_FS_DBLOCK,
+                             NULL,
                              GNUNET_BLOCK_EO_NONE,
                              &key,
                              NULL, 0,
-                             NULL, 0,
                              NULL, 0))
     return 4;
   GNUNET_log_skip (1, GNUNET_NO);
   if (GNUNET_BLOCK_EVALUATION_REQUEST_INVALID !=
       GNUNET_BLOCK_evaluate (ctx,
                              GNUNET_BLOCK_TYPE_FS_DBLOCK,
+                             NULL,
                              GNUNET_BLOCK_EO_NONE,
                              &key,
-                             NULL, 0,
                              "bogus", 5,
                              NULL, 0))
     return 8;
diff --git a/src/gns/plugin_block_gns.c b/src/gns/plugin_block_gns.c
index 8d3e84042..94222e32b 100644
--- a/src/gns/plugin_block_gns.c
+++ b/src/gns/plugin_block_gns.c
@@ -51,6 +51,7 @@
  * @param nonce random value used to seed the group creation
  * @param raw_data optional serialized prior state of the group, NULL if unavailable/fresh
  * @param raw_data_size number of bytes in @a raw_data, 0 if unavailable/fresh
+ * @param va variable arguments specific to @a type
  * @return block group handle, NULL if block groups are not supported
  *         by this @a type of block (this is not an error)
  */
@@ -59,7 +60,8 @@ block_plugin_gns_create_group (void *cls,
                                enum GNUNET_BLOCK_Type type,
                                uint32_t nonce,
                                const void *raw_data,
-                               size_t raw_data_size)
+                               size_t raw_data_size,
+                               va_list va)
 {
   return GNUNET_BLOCK_GROUP_bf_create (cls,
                                        GNS_BF_SIZE,
@@ -80,10 +82,9 @@ block_plugin_gns_create_group (void *cls,
  *
  * @param cls closure
  * @param type block type
+ * @param bg block group to use for evaluation
  * @param eo control flags
  * @param query original query (hash)
- * @param bf pointer to bloom filter associated with @a query; possibly updated (!)
- * @param bf_mutator mutation value for @a bf
  * @param xquery extrended query data (can be NULL, depending on @a type)
  * @param xquery_size number of bytes in @a xquery
  * @param reply_block response to validate
@@ -93,10 +94,9 @@ block_plugin_gns_create_group (void *cls,
 static enum GNUNET_BLOCK_EvaluationResult
 block_plugin_gns_evaluate (void *cls,
                            enum GNUNET_BLOCK_Type type,
+                           struct GNUNET_BLOCK_Group *bg,
                            enum GNUNET_BLOCK_EvaluationOptions eo,
                            const struct GNUNET_HashCode *query,
-                           struct GNUNET_CONTAINER_BloomFilter **bf,
-                           int32_t bf_mutator,
                            const void *xquery,
                            size_t xquery_size,
                            const void *reply_block,
@@ -105,7 +105,6 @@ block_plugin_gns_evaluate (void *cls,
   const struct GNUNET_GNSRECORD_Block *block;
   struct GNUNET_HashCode h;
   struct GNUNET_HashCode chash;
-  struct GNUNET_HashCode mhash;
 
   if (type != GNUNET_BLOCK_TYPE_GNS_NAMERECORD)
     return GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED;
@@ -146,21 +145,13 @@ block_plugin_gns_evaluate (void *cls,
       GNUNET_break_op (0);
       return GNUNET_BLOCK_EVALUATION_RESULT_INVALID;
     }
-  if (NULL != bf)
-    {
-      GNUNET_CRYPTO_hash (reply_block, reply_block_size, &chash);
-      GNUNET_BLOCK_mingle_hash (&chash, bf_mutator, &mhash);
-      if (NULL != *bf)
-        {
-          if (GNUNET_YES == GNUNET_CONTAINER_bloomfilter_test(*bf, &mhash))
-            return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
-        }
-      else
-        {
-          *bf = GNUNET_CONTAINER_bloomfilter_init(NULL, 8, BLOOMFILTER_K);
-        }
-      GNUNET_CONTAINER_bloomfilter_add(*bf, &mhash);
-    }
+  GNUNET_CRYPTO_hash (reply_block,
+                      reply_block_size,
+                      &chash);
+  if (GNUNET_YES ==
+      GNUNET_BLOCK_GROUP_bf_test_and_set (bg,
+                                          &chash))
+    return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
   return GNUNET_BLOCK_EVALUATION_OK_MORE;
 }
 
diff --git a/src/include/gnunet_block_group_lib.h b/src/include/gnunet_block_group_lib.h
index 5fa14ce00..a1ea807f6 100644
--- a/src/include/gnunet_block_group_lib.h
+++ b/src/include/gnunet_block_group_lib.h
@@ -66,6 +66,20 @@ GNUNET_BLOCK_GROUP_bf_create (void *cls,
                               size_t raw_data_size);
 
 
+/**
+ * Test if @a hc is contained in the Bloom filter of @a bg.  If so,
+ * return #GNUNET_YES.  If not, add @a hc to the Bloom filter and
+ * return #GNUNET_NO.
+ *
+ * @param bg block group to use for testing
+ * @param hc hash of element to evaluate
+ * @return #GNUNET_YES if @a hc is (likely) a duplicate
+ *         #GNUNET_NO if @a hc was definitively not in @bg (but now is)
+ */
+int
+GNUNET_BLOCK_GROUP_bf_test_and_set (struct GNUNET_BLOCK_Group *bg,
+                                    const struct GNUNET_HashCode *hc);
+
 
 #if 0                           /* keep Emacsens' auto-indent happy */
 {
diff --git a/src/include/gnunet_block_lib.h b/src/include/gnunet_block_lib.h
index 0f0fee499..a40f33699 100644
--- a/src/include/gnunet_block_lib.h
+++ b/src/include/gnunet_block_lib.h
@@ -245,6 +245,7 @@ struct GNUNET_BLOCK_Group;
  * @param nonce random value used to seed the group creation
  * @param raw_data optional serialized prior state of the group, NULL if unavailable/fresh
  * @param raw_data_size number of bytes in @a raw_data, 0 if unavailable/fresh
+ * @param ... type-specific additional data, can be empty
  * @return block group handle, NULL if block groups are not supported
  *         by this @a type of block (this is not an error)
  */
@@ -253,13 +254,15 @@ GNUNET_BLOCK_group_create (struct GNUNET_BLOCK_Context *ctx,
                            enum GNUNET_BLOCK_Type type,
                            uint32_t nonce,
                            const void *raw_data,
-                           size_t raw_data_size);
+                           size_t raw_data_size,
+                           ...);
 
 
 /**
  * Serialize state of a block group.
  *
  * @param bg group to serialize
+ * @param[out] nonce set to the nonce of the @a bg
  * @param[out] raw_data set to the serialized state
  * @param[out] raw_data_size set to the number of bytes in @a raw_data
  * @return #GNUNET_OK on success, #GNUNET_NO if serialization is not
@@ -267,6 +270,7 @@ GNUNET_BLOCK_group_create (struct GNUNET_BLOCK_Context *ctx,
  */
 int
 GNUNET_BLOCK_group_serialize (struct GNUNET_BLOCK_Group *bg,
+                              uint32_t *nonce,
                               void **raw_data,
                               size_t *raw_data_size);
 
@@ -289,10 +293,9 @@ GNUNET_BLOCK_group_destroy (struct GNUNET_BLOCK_Group *bg);
  *
  * @param ctx block contxt
  * @param type block type
+ * @param group block group to use for evaluation
  * @param eo evaluation options to control evaluation
  * @param query original query (hash)
- * @param bf pointer to bloom filter associated with query; possibly updated (!)
- * @param bf_mutator mutation value for @a bf
  * @param xquery extrended query data (can be NULL, depending on type)
  * @param xquery_size number of bytes in @a xquery
  * @param reply_block response to validate
@@ -302,10 +305,9 @@ GNUNET_BLOCK_group_destroy (struct GNUNET_BLOCK_Group *bg);
 enum GNUNET_BLOCK_EvaluationResult
 GNUNET_BLOCK_evaluate (struct GNUNET_BLOCK_Context *ctx,
                        enum GNUNET_BLOCK_Type type,
+                       struct GNUNET_BLOCK_Group *group,
                        enum GNUNET_BLOCK_EvaluationOptions eo,
                        const struct GNUNET_HashCode *query,
-                       struct GNUNET_CONTAINER_BloomFilter **bf,
-                       int32_t bf_mutator,
                        const void *xquery,
                        size_t xquery_size,
                        const void *reply_block,
@@ -330,24 +332,41 @@ GNUNET_BLOCK_get_key (struct GNUNET_BLOCK_Context *ctx,
                       enum GNUNET_BLOCK_Type type,
                       const void *block,
                       size_t block_size,
-                      struct GNUNET_HashCode * key);
-
+                      struct GNUNET_HashCode *key);
 
 
 /**
- * Construct a bloom filter that would filter out the given
- * results.
+ * Update block group to filter out the given results.  Note that the
+ * use of a hash for seen results implies that the caller magically
+ * knows how the specific block engine hashes for filtering
+ * duplicates, so this API may not always apply.
  *
  * @param bf_mutator mutation value to use
  * @param seen_results results already seen
  * @param seen_results_count number of entries in @a seen_results
- * @return NULL if seen_results_count is 0, otherwise a BF
- *         that would match the given results.
+ * @return #GNUNET_SYSERR if not supported, #GNUNET_OK on success
+ */
+int
+GNUNET_BLOCK_group_set_seen (struct GNUNET_BLOCK_Group *bg,
+                             const struct GNUNET_HashCode *seen_results,
+                             unsigned int seen_results_count);
+
+
+/**
+ * Try merging two block groups.  Afterwards, @a bg1 should remain
+ * valid and contain the rules from both @a bg1 and @bg2, and
+ * @a bg2 should be destroyed (as part of this call).  The latter
+ * should happen even if merging is not supported.
+ *
+ * @param[in,out] bg1 first group to merge, is updated
+ * @param bg2 second group to merge, is destroyed
+ * @return #GNUNET_OK on success,
+ *         #GNUNET_NO if merge failed due to different nonce
+ *         #GNUNET_SYSERR if merging is not supported
  */
-struct GNUNET_CONTAINER_BloomFilter *
-GNUNET_BLOCK_construct_bloomfilter (int32_t bf_mutator,
-                                    const struct GNUNET_HashCode *seen_results,
-                                    unsigned int seen_results_count);
+int
+GNUNET_BLOCK_group_merge (struct GNUNET_BLOCK_Group *bg1,
+                          struct GNUNET_BLOCK_Group *bg2);
 
 
 #if 0                           /* keep Emacsens' auto-indent happy */
diff --git a/src/include/gnunet_block_plugin.h b/src/include/gnunet_block_plugin.h
index d7454b5d5..171b6cfc0 100644
--- a/src/include/gnunet_block_plugin.h
+++ b/src/include/gnunet_block_plugin.h
@@ -40,9 +40,38 @@
 
 
 /**
+ * Mark elements as "seen" using a hash of the element. Not supported
+ * by all block plugins.
+ *
+ * @param bg group to update
+ * @param seen_results results already seen
+ * @param seen_results_count number of entries in @a seen_results
+ */
+typedef void
+(*GNUNET_BLOCK_GroupMarkSeenFunction)(struct GNUNET_BLOCK_Group *bg,
+                                      const struct GNUNET_HashCode *seen_results,
+                                      unsigned int seen_results_count);
+
+
+/**
+ * Merge two groups, if possible. Not supported by all block plugins,
+ * can also fail if the nonces were different.
+ *
+ * @param bg1 group to update
+ * @param bg2 group to merge into @a bg1
+ * @return #GNUNET_OK on success, #GNUNET_NO if the nonces were different and thus
+ *         we failed.
+ */
+typedef int
+(*GNUNET_BLOCK_GroupMergeFunction)(struct GNUNET_BLOCK_Group *bg1,
+                                   const struct GNUNET_BLOCK_Group *bg2);
+
+
+/**
  * Serialize state of a block group.
  *
  * @param bg group to serialize
+ * @param[out] nonce set to the nonce of the @a bg
  * @param[out] raw_data set to the serialized state
  * @param[out] raw_data_size set to the number of bytes in @a raw_data
  * @return #GNUNET_OK on success, #GNUNET_NO if serialization is not
@@ -50,6 +79,7 @@
  */
 typedef int
 (*GNUNET_BLOCK_GroupSerializeFunction)(struct GNUNET_BLOCK_Group *bg,
+                                       uint32_t *nonce,
                                        void **raw_data,
                                        size_t *raw_data_size);
 
@@ -87,6 +117,18 @@ struct GNUNET_BLOCK_Group
   GNUNET_BLOCK_GroupSerializeFunction serialize_cb;
 
   /**
+   * Function to call to mark elements as seen in the group.
+   * Can be NULL if not supported.
+   */
+  GNUNET_BLOCK_GroupMarkSeenFunction mark_seen_cb;
+
+  /**
+   * Function to call to merge two groups.
+   * Can be NULL if not supported.
+   */
+  GNUNET_BLOCK_GroupMergeFunction merge_cb;
+
+  /**
    * Function to call to destroy the block group.
    * Must not be NULL.
    */
@@ -108,6 +150,7 @@ struct GNUNET_BLOCK_Group
  * @param nonce random value used to seed the group creation
  * @param raw_data optional serialized prior state of the group, NULL if unavailable/fresh
  * @param raw_data_size number of bytes in @a raw_data, 0 if unavailable/fresh
+ * @param va variable arguments specific to @a type
  * @return block group handle, NULL if block groups are not supported
  *         by this @a type of block (this is not an error)
  */
@@ -116,7 +159,8 @@ typedef struct GNUNET_BLOCK_Group *
                                     enum GNUNET_BLOCK_Type type,
                                     uint32_t nonce,
                                     const void *raw_data,
-                                    size_t raw_data_size);
+                                    size_t raw_data_size,
+                                    va_list va);
 
 
 /**
@@ -128,10 +172,9 @@ typedef struct GNUNET_BLOCK_Group *
  *
  * @param cls closure
  * @param type block type
+ * @param group which block group to use for evaluation
  * @param eo evaluation options to control evaluation
  * @param query original query (hash)
- * @param bf pointer to bloom filter associated with query; possibly updated (!)
- * @param bf_mutator mutation value for @a bf
  * @param xquery extrended query data (can be NULL, depending on type)
  * @param xquery_size number of bytes in @a xquery
  * @param reply_block response to validate
@@ -141,10 +184,9 @@ typedef struct GNUNET_BLOCK_Group *
 typedef enum GNUNET_BLOCK_EvaluationResult
 (*GNUNET_BLOCK_EvaluationFunction) (void *cls,
                                     enum GNUNET_BLOCK_Type type,
+                                    struct GNUNET_BLOCK_Group *group,
                                     enum GNUNET_BLOCK_EvaluationOptions eo,
                                     const struct GNUNET_HashCode *query,
-                                    struct GNUNET_CONTAINER_BloomFilter **bf,
-                                    int32_t bf_mutator,
                                     const void *xquery,
                                     size_t xquery_size,
                                     const void *reply_block,
diff --git a/src/regex/plugin_block_regex.c b/src/regex/plugin_block_regex.c
index 11511a71b..6636f3cdb 100644
--- a/src/regex/plugin_block_regex.c
+++ b/src/regex/plugin_block_regex.c
@@ -46,6 +46,7 @@
  * @param nonce random value used to seed the group creation
  * @param raw_data optional serialized prior state of the group, NULL if unavailable/fresh
  * @param raw_data_size number of bytes in @a raw_data, 0 if unavailable/fresh
+ * @param va variable arguments specific to @a type
  * @return block group handle, NULL if block groups are not supported
  *         by this @a type of block (this is not an error)
  */
@@ -54,7 +55,8 @@ block_plugin_regex_create_group (void *cls,
                                  enum GNUNET_BLOCK_Type type,
                                  uint32_t nonce,
                                  const void *raw_data,
-                                 size_t raw_data_size)
+                                 size_t raw_data_size,
+                                 va_list va)
 {
   return GNUNET_BLOCK_GROUP_bf_create (cls,
                                        REGEX_BF_SIZE,
@@ -76,10 +78,9 @@ block_plugin_regex_create_group (void *cls,
  *
  * @param cls closure
  * @param type block type
+ * @param bg block group to evaluate against
  * @param eo control flags
  * @param query original query (hash)
- * @param bf pointer to bloom filter associated with query; possibly updated (!)
- * @param bf_mutator mutation value for bf
  * @param xquery extrended query data (can be NULL, depending on type)
  * @param xquery_size number of bytes in @a xquery
  * @param reply_block response to validate
@@ -89,15 +90,16 @@ block_plugin_regex_create_group (void *cls,
 static enum GNUNET_BLOCK_EvaluationResult
 evaluate_block_regex (void *cls,
                       enum GNUNET_BLOCK_Type type,
+                      struct GNUNET_BLOCK_Group *bg,
                       enum GNUNET_BLOCK_EvaluationOptions eo,
                       const struct GNUNET_HashCode *query,
-                      struct GNUNET_CONTAINER_BloomFilter **bf,
-                      int32_t bf_mutator,
                       const void *xquery,
                       size_t xquery_size,
                       const void *reply_block,
                       size_t reply_block_size)
 {
+  struct GNUNET_HashCode chash;
+
   if (NULL == reply_block)
   {
     if (0 != xquery_size)
@@ -146,24 +148,13 @@ evaluate_block_regex (void *cls,
     default:
       break;
   }
-  if (NULL != bf)
-  {
-    struct GNUNET_HashCode chash;
-    struct GNUNET_HashCode mhash;
-
-    GNUNET_CRYPTO_hash (reply_block, reply_block_size, &chash);
-    GNUNET_BLOCK_mingle_hash (&chash, bf_mutator, &mhash);
-    if (NULL != *bf)
-    {
-      if (GNUNET_YES == GNUNET_CONTAINER_bloomfilter_test (*bf, &mhash))
-        return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
-    }
-    else
-    {
-      *bf = GNUNET_CONTAINER_bloomfilter_init (NULL, 8, GNUNET_CONSTANTS_BLOOMFILTER_K);
-    }
-    GNUNET_CONTAINER_bloomfilter_add (*bf, &mhash);
-  }
+  GNUNET_CRYPTO_hash (reply_block,
+                      reply_block_size,
+                      &chash);
+  if (GNUNET_YES ==
+      GNUNET_BLOCK_GROUP_bf_test_and_set (bg,
+                                          &chash))
+    return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
   return GNUNET_BLOCK_EVALUATION_OK_MORE;
 }
 
@@ -178,10 +169,9 @@ evaluate_block_regex (void *cls,
  *
  * @param cls closure
  * @param type block type
+ * @param bg block group to evaluate against
  * @param eo control flags
  * @param query original query (hash)
- * @param bf pointer to bloom filter associated with query; possibly updated (!)
- * @param bf_mutator mutation value for bf
  * @param xquery extrended query data (can be NULL, depending on type)
  * @param xquery_size number of bytes in @a xquery
  * @param reply_block response to validate
@@ -191,14 +181,15 @@ evaluate_block_regex (void *cls,
 static enum GNUNET_BLOCK_EvaluationResult
 evaluate_block_regex_accept (void *cls,
                              enum GNUNET_BLOCK_Type type,
+                             struct GNUNET_BLOCK_Group *bg,
                              enum GNUNET_BLOCK_EvaluationOptions eo,
-                             const struct GNUNET_HashCode * query,
-                             struct GNUNET_CONTAINER_BloomFilter **bf,
-                             int32_t bf_mutator, const void *xquery,
+                             const struct GNUNET_HashCode *query,
+                             const void *xquery,
                              size_t xquery_size, const void *reply_block,
                              size_t reply_block_size)
 {
   const struct RegexAcceptBlock *rba;
+  struct GNUNET_HashCode chash;
 
   if (0 != xquery_size)
   {
@@ -236,24 +227,13 @@ evaluate_block_regex_accept (void *cls,
     GNUNET_break_op(0);
     return GNUNET_BLOCK_EVALUATION_RESULT_INVALID;
   }
-  if (NULL != bf)
-  {
-    struct GNUNET_HashCode chash;
-    struct GNUNET_HashCode mhash;
-
-    GNUNET_CRYPTO_hash (reply_block, reply_block_size, &chash);
-    GNUNET_BLOCK_mingle_hash (&chash, bf_mutator, &mhash);
-    if (NULL != *bf)
-    {
-      if (GNUNET_YES == GNUNET_CONTAINER_bloomfilter_test (*bf, &mhash))
-        return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
-    }
-    else
-    {
-      *bf = GNUNET_CONTAINER_bloomfilter_init (NULL, 8, GNUNET_CONSTANTS_BLOOMFILTER_K);
-    }
-    GNUNET_CONTAINER_bloomfilter_add (*bf, &mhash);
-  }
+  GNUNET_CRYPTO_hash (reply_block,
+                      reply_block_size,
+                      &chash);
+  if (GNUNET_YES ==
+      GNUNET_BLOCK_GROUP_bf_test_and_set (bg,
+                                          &chash))
+    return GNUNET_BLOCK_EVALUATION_OK_DUPLICATE;
   return GNUNET_BLOCK_EVALUATION_OK_MORE;
 }
 
@@ -267,10 +247,9 @@ evaluate_block_regex_accept (void *cls,
  *
  * @param cls closure
  * @param type block type
+ * @param bg group to evaluate against
  * @param eo control flags
  * @param query original query (hash)
- * @param bf pointer to bloom filter associated with query; possibly updated (!)
- * @param bf_mutator mutation value for bf
  * @param xquery extrended query data (can be NULL, depending on type)
  * @param xquery_size number of bytes in xquery
  * @param reply_block response to validate
@@ -280,10 +259,9 @@ evaluate_block_regex_accept (void *cls,
 static enum GNUNET_BLOCK_EvaluationResult
 block_plugin_regex_evaluate (void *cls,
                              enum GNUNET_BLOCK_Type type,
+                             struct GNUNET_BLOCK_Group *bg,
                              enum GNUNET_BLOCK_EvaluationOptions eo,
                              const struct GNUNET_HashCode *query,
-                             struct GNUNET_CONTAINER_BloomFilter **bf,
-                             int32_t bf_mutator,
                              const void *xquery,
                              size_t xquery_size,
                              const void *reply_block,
@@ -296,18 +274,18 @@ block_plugin_regex_evaluate (void *cls,
     case GNUNET_BLOCK_TYPE_REGEX:
       result = evaluate_block_regex (cls,
                                      type,
+                                     bg,
                                      eo,
                                      query,
-                                     bf, bf_mutator,
                                      xquery, xquery_size,
                                      reply_block, reply_block_size);
       break;
     case GNUNET_BLOCK_TYPE_REGEX_ACCEPT:
       result = evaluate_block_regex_accept (cls,
                                             type,
+                                            bg,
                                             eo,
                                             query,
-                                            bf, bf_mutator,
                                             xquery, xquery_size,
                                             reply_block, reply_block_size);
       break;