commit a59f2302373b3ee83cf4d43773d04b5646e0c358
parent fc0aeb61c724488e58c4958305baed4c52168205
Author: Florian Dold <dold@taler.net>
Date: Wed, 9 Sep 2026 01:17:41 +0200
implement invertible bloom filter
Diffstat:
24 files changed, 3008 insertions(+), 10 deletions(-)
diff --git a/src/include/sync/sync-database/lookup_block_hashes_TR.h b/src/include/sync/sync-database/lookup_block_hashes_TR.h
@@ -0,0 +1,61 @@
+/*
+ This file is part of GNU Taler
+ Copyright (C) 2026 Taler Systems SA
+
+ Taler is free software; you can redistribute it and/or modify it under the
+ terms of the GNU Lesser General Public License as published by the Free Software
+ Foundation; either version 3, or (at your option) any later version.
+
+ Taler is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License along with
+ Taler; see the file COPYING.GPL. If not, see <http://www.gnu.org/licenses/>
+*/
+/**
+ * @file include/sync/sync-database/lookup_block_hashes_TR.h
+ * @brief lookup the hashes of all the blocks of an account
+ * @author Iván Ávalos
+ */
+#ifndef SYNC_DATABASE_LOOKUP_BLOCK_HASHES_TR_H
+#define SYNC_DATABASE_LOOKUP_BLOCK_HASHES_TR_H
+
+#include "sync/sync_service.h"
+
+
+/**
+ * Iterator called for every block returned by the query.
+ *
+ * @param cls closure pointer
+ * @param nonce nonce identifying the block
+ * @param block_hash hash of the block data
+ */
+typedef void
+(*SYNC_DB_BlockHashIterator)(void *cls,
+ const struct SYNC_BlockNonce *nonce,
+ const struct GNUNET_HashCode *block_hash);
+
+
+/**
+ * Lookup the identities of all the blocks in the account's linked
+ * list. The @a it iterator is called for every block, in arbitrary
+ * order.
+ *
+ * @param account_pub account to look the blocks up for
+ * @param it iterator to call for every block (may be NULL to only
+ * count the blocks)
+ * @param it_cls closure for @a it
+ * @return number of blocks found,
+ * #SYNC_DB_NO_RESULTS if the account has no blocks,
+ * #SYNC_DB_PAYMENT_REQUIRED if the account does not exist,
+ * #SYNC_DB_HARD_ERROR or #SYNC_DB_SOFT_ERROR on database
+ * errors
+ */
+enum SYNC_DB_QueryStatus
+SYNCDB_lookup_block_hashes_TR (
+ const struct SYNC_AccountPublicKeyP *account_pub,
+ SYNC_DB_BlockHashIterator it,
+ void *it_cls);
+
+#endif
+\ No newline at end of file
diff --git a/src/include/sync/sync_database_lib.h b/src/include/sync/sync_database_lib.h
@@ -30,6 +30,7 @@
#include <sync/sync-database/update_block_TR.h>
#include <sync/sync-database/increment_lifetime_TR.h>
#include <sync/sync-database/lookup_block_range_TR.h>
+#include <sync/sync-database/lookup_block_hashes_TR.h>
#include <sync/sync-database/lookup_account_TR.h>
#include <sync/sync-database/lookup_block_TR.h>
#include <sync/sync-database/lookup_object.h>
diff --git a/src/include/sync/sync_ibf.h b/src/include/sync/sync_ibf.h
@@ -0,0 +1,211 @@
+/*
+ This file is part of TALER
+ Copyright (C) 2026 Taler Systems SA
+
+ TALER is free software; you can redistribute it and/or modify it under the
+ terms of the GNU Affero General Public License as published by the Free Software
+ Foundation; either version 3, or (at your option) any later version.
+
+ TALER is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details.
+
+ You should have received a copy of the GNU Affero General Public License along with
+ TALER; see the file COPYING. If not, see <http://www.gnu.org/licenses/>
+*/
+/**
+ * @file include/sync/sync_ibf.h
+ * @brief invertible bloom filter for backup reconciliation (DD 92)
+ * @author Iván Ávalos
+ */
+#ifndef SYNC_IBF_H
+#define SYNC_IBF_H
+
+#include <gnunet/gnunet_util_lib.h>
+
+
+/**
+ * Number of hash functions used when the server computes the
+ * reconciliation filter of an account.
+ */
+#define SYNC_IBF_HASH_NUM 3
+
+/**
+ * Minimum number of buckets a filter is built with.
+ */
+#define SYNC_IBF_MIN_BUCKETS 64
+
+/**
+ * Maximum number of buckets a filter is built with (bounds the size
+ * of the serialized filter to
+ * #SYNC_IBF_MAX_BUCKETS * #SYNC_IBF_BUCKET_SIZE).
+ */
+#define SYNC_IBF_MAX_BUCKETS 4096
+
+/**
+ * Size of one element: the 24-byte block nonce followed by the
+ * 64-byte block hash.
+ */
+#define SYNC_IBF_KEY_SIZE 88
+
+/**
+ * Size of the key hash sum stored per bucket, in bytes.
+ */
+#define SYNC_IBF_KEY_HASH_SIZE 8
+
+/**
+ * Size of one bucket: 2-byte counter + key sum + key hash sum.
+ */
+#define SYNC_IBF_BUCKET_SIZE (2 + SYNC_IBF_KEY_SIZE + SYNC_IBF_KEY_HASH_SIZE)
+
+
+/**
+ * One element of the filter: the identity of a block.
+ */
+struct SYNC_IBFKey
+{
+ /**
+ * Nonce identifying the block.
+ */
+ unsigned char nonce[24];
+
+ /**
+ * Hash of the block data.
+ */
+ unsigned char hash[64];
+};
+
+
+/**
+ * Compute the number of buckets to use for a filter built over
+ * @a block_count blocks, sized so that small differences decode while
+ * the serialized filter stays bounded.
+ *
+ * @param block_count expected number of elements in the filter
+ * @return number of buckets to use (a power of two within
+ * [#SYNC_IBF_MIN_BUCKETS, #SYNC_IBF_MAX_BUCKETS])
+ */
+uint32_t
+SYNC_ibf_compute_bucket_count (uint32_t block_count);
+
+
+/**
+ * Create a fresh invertible bloom filter.
+ *
+ * @param bucket_count number of buckets
+ * @param hash_num number of hash functions per element
+ * @param prefix mixing salt hashed with every element (4 bytes,
+ * network byte order, zero for the default)
+ * @return the filter, NULL on failure
+ */
+struct SYNC_IBF *
+SYNC_ibf_create (uint32_t bucket_count,
+ unsigned int hash_num,
+ uint32_t prefix);
+
+
+/**
+ * Create a filter from its serialized state.
+ *
+ * @param data serialized filter of @a bucket_count buckets
+ * (see #SYNC_ibf_serialize())
+ * @param bucket_count number of buckets the serialized filter holds
+ * @param hash_num number of hash functions per element
+ * @param prefix mixing salt the serialized filter was built with
+ * @return the filter, NULL on failure
+ */
+struct SYNC_IBF *
+SYNC_ibf_deserialize (const void *data,
+ uint32_t bucket_count,
+ unsigned int hash_num,
+ uint32_t prefix);
+
+
+/**
+ * Number of bytes of the serialized filter.
+ *
+ * @param ibf filter to measure
+ * @return size in bytes, 0 if @a ibf is NULL
+ */
+size_t
+SYNC_ibf_get_serialized_size (const struct SYNC_IBF *ibf);
+
+
+/**
+ * Serialize the filter into @a data (network byte order).
+ *
+ * @param ibf filter to serialize
+ * @param data where to write the serialized filter
+ */
+void
+SYNC_ibf_serialize (const struct SYNC_IBF *ibf,
+ void *data);
+
+
+/**
+ * Free the filter.
+ *
+ * @param ibf filter to free, NULL is allowed
+ */
+void
+SYNC_ibf_destroy (struct SYNC_IBF *ibf);
+
+
+/**
+ * Insert an element into the filter.
+ *
+ * @param ibf filter to insert into
+ * @param key element to insert
+ */
+void
+SYNC_ibf_insert (struct SYNC_IBF *ibf,
+ const struct SYNC_IBFKey *key);
+
+
+/**
+ * Remove an element from the filter (must have been inserted).
+ *
+ * @param ibf filter to remove from
+ * @param key element to remove
+ */
+void
+SYNC_ibf_remove (struct SYNC_IBF *ibf,
+ const struct SYNC_IBFKey *key);
+
+
+/**
+ * Subtract @a ibf2 from @a ibf1, storing the result in @a ibf1.
+ * Both filters must have the same parameters.
+ *
+ * The result is the filter one would get from inserting exactly the
+ * elements that differ between the two original sets; decoding it
+ * enumerates them.
+ *
+ * @param ibf1 filter that is subtracted from
+ * @param ibf2 filter that is subtracted
+ */
+void
+SYNC_ibf_subtract (struct SYNC_IBF *ibf1,
+ const struct SYNC_IBF *ibf2);
+
+
+/**
+ * Decode and remove one element from the filter, peeling a pure
+ * bucket.
+ *
+ * @param ibf the filter to decode from
+ * @param[out] ret_side +1 if the element is only in ibf1 of a
+ * subtraction, -1 if it is only in ibf2
+ * @param[out] ret_key where to store the decoded element
+ * @return #GNUNET_YES if an element was decoded,
+ * #GNUNET_NO if the filter is empty,
+ * #GNUNET_SYSERR if the filter cannot be decoded (too many
+ * colliding elements for its size)
+ */
+enum GNUNET_GenericReturnValue
+SYNC_ibf_decode (struct SYNC_IBF *ibf,
+ int16_t *ret_side,
+ struct SYNC_IBFKey *ret_key);
+
+
+#endif /* SYNC_IBF_H */
+\ No newline at end of file
diff --git a/src/include/sync/sync_service.h b/src/include/sync/sync_service.h
@@ -228,6 +228,114 @@ void
SYNC_block_list_cancel (struct SYNC_BlockListOperation *op);
+/* ********************* Block reconcile API *********************** */
+
+
+/**
+ * Result of a block reconcile (bloom filter) operation, as returned
+ * by GET /backups/$KEY/blocks/reconcile.
+ */
+struct SYNC_ReconcileDetails
+{
+
+ /**
+ * HTTP status code.
+ */
+ unsigned int http_status;
+
+ /**
+ * Taler error code.
+ */
+ enum TALER_ErrorCode ec;
+
+ /**
+ * Version of the filter format.
+ */
+ uint32_t version;
+
+ /**
+ * Number of 32-bit buckets in the filter.
+ */
+ uint32_t bucket_count;
+
+ /**
+ * Number of bits set per element.
+ */
+ unsigned int k;
+
+ /**
+ * Mixing prefix the filter was built with.
+ */
+ uint32_t prefix;
+
+ /**
+ * Number of blocks in the account's linked list.
+ */
+ uint32_t total_blocks;
+
+ /**
+ * Number of bytes in @e data.
+ */
+ size_t data_size;
+
+ /**
+ * Serialized bloom filter (bucket_count * 4 bytes), allocated by
+ * the parser and freed by the client after the callback returns.
+ */
+ void *data;
+
+};
+
+
+/**
+ * Callback for the reconcile operation.
+ *
+ * @param cls closure
+ * @param rd result details (only valid during the callback)
+ */
+typedef void
+(*SYNC_ReconcileCallback)(void *cls,
+ const struct SYNC_ReconcileDetails *rd);
+
+
+/**
+ * Handle for a block reconcile operation.
+ */
+struct SYNC_ReconcileOperation;
+
+
+/**
+ * Fetch the bloom filter over the hashes of all the blocks of an
+ * account, used by wallets to reconcile their local copy of the
+ * backup with the server's (DD 92).
+ *
+ * @param ctx for HTTP client request processing
+ * @param base_url base URL of the Sync server
+ * @param pub account public key
+ * @param prefix optional mixing prefix to rebuild the filter with
+ * (used to get rid of false positives), NULL for the default
+ * @param cb function to call with the result
+ * @param cb_cls closure for @a cb
+ * @return handle for the operation
+ */
+struct SYNC_ReconcileOperation *
+SYNC_block_reconcile (struct GNUNET_CURL_Context *ctx,
+ const char *base_url,
+ const struct SYNC_AccountPublicKeyP *pub,
+ const uint32_t *prefix,
+ SYNC_ReconcileCallback cb,
+ void *cb_cls);
+
+
+/**
+ * Cancel a block reconcile operation.
+ *
+ * @param[in] op operation to cancel
+ */
+void
+SYNC_block_reconcile_cancel (struct SYNC_ReconcileOperation *op);
+
+
/* ********************* Block operation API *********************** */
diff --git a/src/include/sync/sync_testing_lib.h b/src/include/sync/sync_testing_lib.h
@@ -144,6 +144,56 @@ SYNC_TESTING_cmd_block_list (const char *label,
/**
+ * Make the "block reconcile" command: fetch the invertible bloom
+ * filter over the account's blocks (DD 92), rebuild the wallet's side
+ * of the reconciliation over the locally held blocks, and verify that
+ * the decoded difference is exactly as expected.
+ *
+ * @param label command label
+ * @param sync_url base URL of the sync serving
+ * @param account_reference reference to a previous command that
+ * provides the account public key
+ * @param http_status expected HTTP status.
+ * @param expected_total_blocks expected number of blocks the filter
+ * must report
+ * @param prefix optional mixing salt to request (NULL for none);
+ * the reply's prefix must match it
+ * @param num_local number of blocks the wallet holds locally
+ * @param local_nonces nonces of the locally held blocks
+ * (length @a num_local)
+ * @param local_hashes hashes of the locally held blocks
+ * (length @a num_local)
+ * @param num_missing number of blocks expected to be missing locally
+ * @param missing_nonces nonces of the blocks expected missing
+ * (length @a num_missing)
+ * @param missing_hashes hashes of the blocks expected missing
+ * (length @a num_missing)
+ * @param num_stale number of blocks expected to be stale locally
+ * @param stale_nonces nonces of the blocks expected stale
+ * (length @a num_stale)
+ * @param stale_hashes hashes of the blocks expected stale
+ * (length @a num_stale)
+ * @return the command
+ */
+struct TALER_TESTING_Command
+SYNC_TESTING_cmd_block_reconcile (const char *label,
+ const char *sync_url,
+ const char *account_reference,
+ unsigned int http_status,
+ uint32_t expected_total_blocks,
+ const uint32_t *prefix,
+ unsigned int num_local,
+ const struct SYNC_BlockNonce *local_nonces,
+ const struct GNUNET_HashCode *local_hashes,
+ unsigned int num_missing,
+ const struct SYNC_BlockNonce *missing_nonces,
+ const struct GNUNET_HashCode *missing_hashes,
+ unsigned int num_stale,
+ const struct SYNC_BlockNonce *stale_nonces,
+ const struct GNUNET_HashCode *stale_hashes);
+
+
+/**
* Make the "block delete" command.
*
* @param label command label
diff --git a/src/lib/meson.build b/src/lib/meson.build
@@ -7,6 +7,7 @@ libsync_SOURCES = [
'sync_api_block_update.c',
'sync_api_block_delete.c',
'sync_api_block_list.c',
+ 'sync_api_block_reconcile.c',
'sync_api_object_upload.c',
'sync_api_object_fetch.c',
]
diff --git a/src/lib/sync_api_block_reconcile.c b/src/lib/sync_api_block_reconcile.c
@@ -0,0 +1,336 @@
+/*
+ This file is part of TALER
+ Copyright (C) 2026 Taler Systems SA
+
+ TALER is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 3, or
+ (at your option) any later version.
+
+ TALER is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public
+ License along with TALER; see the file COPYING. If not, see
+ <http://www.gnu.org/licenses/>
+*/
+/**
+ * @file lib/sync_api_block_reconcile.c
+ * @brief Implementation of the block reconcile GET
+ * @author Iván Ávalos
+ */
+#include "platform.h"
+#include <curl/curl.h>
+#include <jansson.h>
+#include <microhttpd.h>
+#include <gnunet/gnunet_util_lib.h>
+#include <gnunet/gnunet_curl_lib.h>
+#include <gnunet/gnunet_json_lib.h>
+#include <taler/taler_json_lib.h>
+#include <taler/taler_curl_lib.h>
+#include <sync/sync_service.h>
+#include <sync/sync_util.h>
+#include <sync/sync_ibf.h>
+#include "sync_api_curl_defaults.h"
+
+
+/**
+ * Filter format version accepted by this client.
+ */
+#define SYNC_RECONCILE_VERSION 2
+
+
+/**
+ * Handle for a block reconcile operation.
+ */
+struct SYNC_ReconcileOperation
+{
+
+ /**
+ * The url for this request.
+ */
+ char *url;
+
+ /**
+ * Handle for the request.
+ */
+ struct GNUNET_CURL_Job *job;
+
+ /**
+ * Reference to the execution context.
+ */
+ struct GNUNET_CURL_Context *ctx;
+
+ /**
+ * Function to call with the result.
+ */
+ SYNC_ReconcileCallback cb;
+
+ /**
+ * Closure for @e cb.
+ */
+ void *cb_cls;
+
+};
+
+
+/**
+ * Function called when we're done processing the
+ * GET /backups/$KEY/blocks/reconcile request.
+ *
+ * @param cls the `struct SYNC_ReconcileOperation *`
+ * @param response_code HTTP response code, 0 on error
+ * @param response response body as parsed JSON, or NULL
+ */
+static void
+handle_reconcile_finished (void *cls,
+ long response_code,
+ const void *response)
+{
+ struct SYNC_ReconcileOperation *op = cls;
+ const json_t *json = response;
+ struct SYNC_ReconcileDetails rd = {
+ .http_status = (unsigned int) response_code,
+ .ec = TALER_EC_INVALID
+ };
+
+ op->job = NULL;
+ switch (response_code)
+ {
+ case 0:
+ break;
+ case MHD_HTTP_OK:
+ if (NULL != json)
+ {
+ const json_t *j;
+ const char *filter_s;
+ size_t filter_len;
+
+ /* version */
+ j = json_object_get (json,
+ "version");
+ if ( (NULL == j) ||
+ (! json_is_integer (j)) ||
+ (SYNC_RECONCILE_VERSION != json_integer_value (j)) )
+ {
+ GNUNET_break_op (0);
+ rd.ec = TALER_EC_GENERIC_PARAMETER_MALFORMED;
+ break;
+ }
+ rd.version = (uint32_t) json_integer_value (j);
+ /* bucket_count */
+ j = json_object_get (json,
+ "bucket_count");
+ if ( (NULL == j) ||
+ (! json_is_integer (j)) ||
+ (json_integer_value (j) <= 0) )
+ {
+ GNUNET_break_op (0);
+ rd.ec = TALER_EC_GENERIC_PARAMETER_MALFORMED;
+ break;
+ }
+ rd.bucket_count = (uint32_t) json_integer_value (j);
+ /* k */
+ j = json_object_get (json,
+ "k");
+ if ( (NULL == j) ||
+ (! json_is_integer (j)) ||
+ (json_integer_value (j) <= 0) )
+ {
+ GNUNET_break_op (0);
+ rd.ec = TALER_EC_GENERIC_PARAMETER_MALFORMED;
+ break;
+ }
+ rd.k = (unsigned int) json_integer_value (j);
+ /* prefix */
+ j = json_object_get (json,
+ "prefix");
+ if (NULL == j)
+ {
+ GNUNET_break_op (0);
+ rd.ec = TALER_EC_GENERIC_PARAMETER_MALFORMED;
+ break;
+ }
+ {
+ const char *prefix_s = json_string_value (j);
+ uint32_t prefix;
+
+ if ( (NULL == prefix_s) ||
+ (GNUNET_OK !=
+ GNUNET_STRINGS_string_to_data (prefix_s,
+ strlen (prefix_s),
+ &prefix,
+ sizeof (prefix))) )
+ {
+ GNUNET_break_op (0);
+ rd.ec = TALER_EC_GENERIC_PARAMETER_MALFORMED;
+ break;
+ }
+ rd.prefix = ntohl (prefix);
+ }
+ /* total_blocks */
+ j = json_object_get (json,
+ "total_blocks");
+ if ( (NULL == j) ||
+ (! json_is_integer (j)) ||
+ (json_integer_value (j) < 0) )
+ {
+ GNUNET_break_op (0);
+ rd.ec = TALER_EC_GENERIC_PARAMETER_MALFORMED;
+ break;
+ }
+ rd.total_blocks = (uint32_t) json_integer_value (j);
+ /* filter */
+ j = json_object_get (json,
+ "filter");
+ if (NULL == j)
+ {
+ GNUNET_break_op (0);
+ rd.ec = TALER_EC_GENERIC_PARAMETER_MALFORMED;
+ break;
+ }
+ filter_s = json_string_value (j);
+ if (NULL == filter_s)
+ {
+ GNUNET_break_op (0);
+ rd.ec = TALER_EC_GENERIC_PARAMETER_MALFORMED;
+ break;
+ }
+ rd.data_size = ((size_t) rd.bucket_count) * SYNC_IBF_BUCKET_SIZE;
+ rd.data = GNUNET_malloc (rd.data_size);
+ filter_len = strlen (filter_s);
+ if (GNUNET_OK !=
+ GNUNET_STRINGS_string_to_data (filter_s,
+ filter_len,
+ rd.data,
+ rd.data_size))
+ {
+ GNUNET_free (rd.data);
+ rd.data = NULL;
+ rd.data_size = 0;
+ GNUNET_break_op (0);
+ rd.ec = TALER_EC_GENERIC_PARAMETER_MALFORMED;
+ break;
+ }
+ rd.ec = TALER_EC_NONE;
+ }
+ else
+ {
+ rd.ec = TALER_EC_GENERIC_INVALID_RESPONSE;
+ }
+ break;
+ case MHD_HTTP_BAD_REQUEST:
+ case MHD_HTTP_NOT_FOUND:
+ case MHD_HTTP_PAYMENT_REQUIRED:
+ case MHD_HTTP_INTERNAL_SERVER_ERROR:
+ default:
+ if ( (response_code >= 400) &&
+ (response_code < 500) )
+ rd.ec = (NULL != json)
+ ? TALER_JSON_get_error_code (json)
+ : TALER_EC_GENERIC_PARAMETER_MALFORMED;
+ else if (response_code >= 500)
+ rd.ec = (NULL != json)
+ ? TALER_JSON_get_error_code (json)
+ : TALER_EC_GENERIC_INVALID_RESPONSE;
+ break;
+ }
+
+ if (NULL != op->cb)
+ {
+ op->cb (op->cb_cls,
+ &rd);
+ op->cb = NULL;
+ }
+ GNUNET_free (rd.data);
+ SYNC_block_reconcile_cancel (op);
+}
+
+
+struct SYNC_ReconcileOperation *
+SYNC_block_reconcile (struct GNUNET_CURL_Context *ctx,
+ const char *base_url,
+ const struct SYNC_AccountPublicKeyP *pub,
+ const uint32_t *prefix,
+ SYNC_ReconcileCallback cb,
+ void *cb_cls)
+{
+ struct SYNC_ReconcileOperation *op;
+ CURL *eh;
+ char *pub_s;
+ char *path;
+ char *url;
+
+ pub_s = GNUNET_STRINGS_data_to_string_alloc (pub,
+ sizeof (*pub));
+ GNUNET_asprintf (&path,
+ "backups/%s/blocks/reconcile",
+ pub_s);
+ GNUNET_free (pub_s);
+ if (NULL != prefix)
+ {
+ uint32_t prefix_be = htonl (*prefix);
+ char *prefix_s;
+
+ prefix_s = GNUNET_STRINGS_data_to_string_alloc (&prefix_be,
+ sizeof (prefix_be));
+ url = TALER_url_join (base_url,
+ path,
+ "prefix",
+ prefix_s,
+ NULL);
+ GNUNET_free (prefix_s);
+ }
+ else
+ {
+ url = TALER_url_join (base_url,
+ path,
+ NULL);
+ }
+ GNUNET_free (path);
+ if (NULL == url)
+ {
+ GNUNET_break (0);
+ return NULL;
+ }
+
+ op = GNUNET_new (struct SYNC_ReconcileOperation);
+ op->ctx = ctx;
+ op->cb = cb;
+ op->cb_cls = cb_cls;
+ op->url = url;
+
+ eh = SYNC_curl_easy_get_ (op->url);
+ if (NULL == eh)
+ {
+ GNUNET_break (0);
+ GNUNET_free (op->url);
+ GNUNET_free (op);
+ return NULL;
+ }
+
+ op->job = GNUNET_CURL_job_add2 (ctx,
+ eh,
+ NULL,
+ &handle_reconcile_finished,
+ op);
+ return op;
+}
+
+
+void
+SYNC_block_reconcile_cancel (struct SYNC_ReconcileOperation *op)
+{
+ if (NULL != op->job)
+ {
+ GNUNET_CURL_job_cancel (op->job);
+ op->job = NULL;
+ }
+ GNUNET_free (op->url);
+ GNUNET_free (op);
+}
+
+
+/* end of sync_api_block_reconcile.c */
+\ No newline at end of file
diff --git a/src/sync/meson.build b/src/sync/meson.build
@@ -12,6 +12,7 @@ executable(
'sync-httpd2_post-backups-KEY-objects-UID.c',
'sync-httpd2_get-backups-KEY.c',
'sync-httpd2_get-backups-KEY-blocks.c',
+ 'sync-httpd2_get-backups-KEY-blocks-reconcile.c',
'sync-httpd2_payments.c',
],
dependencies: [
diff --git a/src/sync/sync-httpd2.c b/src/sync/sync-httpd2.c
@@ -30,6 +30,7 @@
#include "sync-httpd2_post-backups-KEY-objects-UID.h"
#include "sync-httpd2_get-backups-KEY.h"
#include "sync-httpd2_get-backups-KEY-blocks.h"
+#include "sync-httpd2_get-backups-KEY-blocks-reconcile.h"
/**
@@ -340,6 +341,13 @@ handle_backup_subpath (struct MHD_Request *request,
.nargs = 0,
},
{
+ .operation = "blocks",
+ .method = MHD_HTTP_METHOD_GET,
+ .handler = &SH_backup_blocks_reconcile_get,
+ .nargs = 1,
+ .nargs_is_upper_bound = true,
+ },
+ {
.operation = "objects",
.method = MHD_HTTP_METHOD_GET,
.handler = &SH_backup_object_get,
@@ -419,12 +427,10 @@ handle_backup_subpath (struct MHD_Request *request,
? (nargs > bh->nargs)
: (nargs != bh->nargs))
{
- GNUNET_break_op (0);
- return TALER_MHD2_reply_with_error (
- request,
- MHD_HTTP_STATUS_NOT_FOUND,
- TALER_EC_GENERIC_ENDPOINT_UNKNOWN,
- subpath);
+ /* Not this handler's shape; there may be another handler for
+ the same (operation, method) with a different number of
+ arguments (e.g. GET blocks vs. GET blocks/reconcile). */
+ continue;
}
return bh->handler (request,
account_pub,
diff --git a/src/sync/sync-httpd2_get-backups-KEY-blocks-reconcile.c b/src/sync/sync-httpd2_get-backups-KEY-blocks-reconcile.c
@@ -0,0 +1,283 @@
+/*
+ This file is part of TALER
+ Copyright (C) 2026 Taler Systems SA
+
+ TALER is free software; you can redistribute it and/or modify it under the
+ terms of the GNU Affero General Public License as published by the Free Software
+ Foundation; either version 3, or (at your option) any later version.
+
+ TALER is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details.
+
+ You should have received a copy of the GNU Affero General Public License along with
+ TALER; see the file COPYING. If not, see <http://www.gnu.org/licenses/>
+*/
+/**
+ * @file sync-httpd2_get-backups-KEY-blocks-reconcile.c
+ * @brief GET /backups/$KEY/blocks/reconcile — invertible bloom filter
+ * over the account's blocks (DD 92)
+ * @author Iván Ávalos
+ */
+#include "sync-httpd2.h"
+#include "sync-httpd2_get-backups-KEY-blocks-reconcile.h"
+#include <gnunet/gnunet_json_lib.h>
+#include <taler/taler_json_lib.h>
+#include <sync/sync_util.h>
+#include <sync/sync_ibf.h>
+
+
+/**
+ * Version of the filter format served by this endpoint.
+ */
+#define SYNC_RECONCILE_VERSION 2
+
+
+/**
+ * Iterator context for collecting the block identities into the
+ * invertible bloom filter.
+ */
+struct ReconcileHashContext
+{
+ /**
+ * Filter being built.
+ */
+ struct SYNC_IBF *ibf;
+
+ /**
+ * Number of blocks fed into the filter (sanity check against the
+ * counting pass).
+ */
+ uint32_t count;
+};
+
+
+/**
+ * Iterator called for every block of the account, adding its identity
+ * (nonce + hash) to the filter.
+ *
+ * @param cls a `struct ReconcileHashContext *`
+ * @param nonce nonce identifying the block
+ * @param block_hash hash of the block data
+ */
+static void
+reconcile_block_iter (void *cls,
+ const struct SYNC_BlockNonce *nonce,
+ const struct GNUNET_HashCode *block_hash)
+{
+ struct ReconcileHashContext *rhc = cls;
+ struct SYNC_IBFKey key;
+
+ rhc->count++;
+ memcpy (key.nonce,
+ nonce,
+ sizeof (key.nonce));
+ memcpy (key.hash,
+ block_hash,
+ sizeof (key.hash));
+ SYNC_ibf_insert (rhc->ibf,
+ &key);
+}
+
+
+const struct MHD_Action *
+SH_backup_blocks_reconcile_get (struct MHD_Request *request,
+ const struct SYNC_AccountPublicKeyP *account_pub
+ ,
+ const char *const args[],
+ uint_fast64_t upload_size,
+ bool is_update)
+{
+ struct ReconcileHashContext rhc;
+ enum SYNC_DB_QueryStatus qs;
+ uint32_t total_blocks;
+ uint32_t bucket_count;
+ uint32_t prefix = 0;
+ struct MHD_StringNullable prefix_str;
+
+ (void) args;
+ (void) upload_size;
+ (void) is_update;
+
+ /* Optional "prefix" query parameter: a fresh mixing salt to rebuild
+ the filter with (4 bytes, base32, network byte order). */
+ if (MHD_YES ==
+ MHD_request_get_value (request,
+ MHD_VK_URI_QUERY_PARAM,
+ "prefix",
+ &prefix_str))
+ {
+ uint32_t prefix_be;
+
+ if ( (NULL == prefix_str.cstr) ||
+ (GNUNET_OK !=
+ GNUNET_STRINGS_string_to_data (prefix_str.cstr,
+ prefix_str.len,
+ &prefix_be,
+ sizeof (prefix_be))) )
+ return TALER_MHD2_reply_with_error (
+ request,
+ MHD_HTTP_STATUS_BAD_REQUEST,
+ TALER_EC_GENERIC_PARAMETER_MALFORMED,
+ "prefix");
+ prefix = ntohl (prefix_be);
+ }
+
+ /* Counting pass: how many blocks does the account hold? This
+ decides the size of the filter. */
+ qs = SYNCDB_lookup_block_hashes_TR (account_pub,
+ NULL,
+ NULL);
+
+ switch (qs)
+ {
+ case SYNC_DB_NO_RESULTS:
+ total_blocks = 0;
+ break;
+
+ case SYNC_DB_PAYMENT_REQUIRED:
+ /* Deliberately not 404, mirroring GET /backups/$KEY/blocks: the
+ account does not exist until it has been paid for. */
+ return TALER_MHD2_reply_with_error (
+ request,
+ MHD_HTTP_STATUS_PAYMENT_REQUIRED,
+ TALER_EC_SYNC_ACCOUNT_UNKNOWN,
+ NULL);
+
+ case SYNC_DB_HARD_ERROR:
+ GNUNET_break (0);
+ return TALER_MHD2_reply_with_error (
+ request,
+ MHD_HTTP_STATUS_INTERNAL_SERVER_ERROR,
+ TALER_EC_GENERIC_DB_FETCH_FAILED,
+ NULL);
+
+ case SYNC_DB_SOFT_ERROR:
+ GNUNET_break (0);
+ return TALER_MHD2_reply_with_error (
+ request,
+ MHD_HTTP_STATUS_INTERNAL_SERVER_ERROR,
+ TALER_EC_GENERIC_DB_SOFT_FAILURE,
+ NULL);
+
+ default:
+ if (qs < 0)
+ {
+ GNUNET_break (0);
+ return TALER_MHD2_reply_with_error (
+ request,
+ MHD_HTTP_STATUS_INTERNAL_SERVER_ERROR,
+ TALER_EC_SYNC_GENERIC_BACKEND_ERROR,
+ NULL);
+ }
+ total_blocks = (uint32_t) qs;
+ break;
+ }
+
+ /* An empty account yields an empty (all-zero) filter: a wallet
+ with nothing to reconcile sees total_blocks 0 and is done. */
+ if (0 == total_blocks)
+ bucket_count = SYNC_IBF_MIN_BUCKETS;
+ else
+ bucket_count = SYNC_ibf_compute_bucket_count (total_blocks);
+ rhc.ibf = SYNC_ibf_create (bucket_count,
+ SYNC_IBF_HASH_NUM,
+ prefix);
+ if (NULL == rhc.ibf)
+ {
+ GNUNET_break (0);
+ return TALER_MHD2_reply_with_error (
+ request,
+ MHD_HTTP_STATUS_INTERNAL_SERVER_ERROR,
+ TALER_EC_GENERIC_INTERNAL_INVARIANT_FAILURE,
+ NULL);
+ }
+
+ /* Streaming pass: build the filter over the block identities. */
+ if (0 < total_blocks)
+ {
+ rhc.count = 0;
+ qs = SYNCDB_lookup_block_hashes_TR (account_pub,
+ &reconcile_block_iter,
+ &rhc);
+ if (qs < 0)
+ {
+ GNUNET_break (0);
+ SYNC_ibf_destroy (rhc.ibf);
+ return TALER_MHD2_reply_with_error (
+ request,
+ MHD_HTTP_STATUS_INTERNAL_SERVER_ERROR,
+ TALER_EC_GENERIC_DB_FETCH_FAILED,
+ NULL);
+ }
+ GNUNET_assert (qs == (enum SYNC_DB_QueryStatus) total_blocks);
+ GNUNET_assert (rhc.count == total_blocks);
+ }
+
+ /* Serialize (network byte order) and base32-encode. */
+ {
+ size_t filter_size;
+ char *filter_s;
+
+ filter_size = SYNC_ibf_get_serialized_size (rhc.ibf);
+ {
+ void *filter_data = GNUNET_malloc (filter_size);
+
+ SYNC_ibf_serialize (rhc.ibf,
+ filter_data);
+ filter_s = GNUNET_STRINGS_data_to_string_alloc (filter_data,
+ filter_size);
+ GNUNET_free (filter_data);
+ }
+ SYNC_ibf_destroy (rhc.ibf);
+ if (NULL == filter_s)
+ {
+ GNUNET_break (0);
+ return TALER_MHD2_reply_with_error (
+ request,
+ MHD_HTTP_STATUS_INTERNAL_SERVER_ERROR,
+ TALER_EC_GENERIC_INTERNAL_INVARIANT_FAILURE,
+ NULL);
+ }
+ {
+ uint32_t prefix_be = htonl (prefix);
+ char *prefix_s;
+ json_t *resp;
+
+ prefix_s = GNUNET_STRINGS_data_to_string_alloc (&prefix_be,
+ sizeof (prefix_be));
+ if (NULL == prefix_s)
+ {
+ GNUNET_break (0);
+ GNUNET_free (filter_s);
+ return TALER_MHD2_reply_with_error (
+ request,
+ MHD_HTTP_STATUS_INTERNAL_SERVER_ERROR,
+ TALER_EC_GENERIC_INTERNAL_INVARIANT_FAILURE,
+ NULL);
+ }
+ resp = GNUNET_JSON_PACK (
+ GNUNET_JSON_pack_uint64 ("version",
+ SYNC_RECONCILE_VERSION),
+ GNUNET_JSON_pack_uint64 ("bucket_count",
+ bucket_count),
+ GNUNET_JSON_pack_uint64 ("k",
+ SYNC_IBF_HASH_NUM),
+ GNUNET_JSON_pack_string ("prefix",
+ prefix_s),
+ GNUNET_JSON_pack_uint64 ("total_blocks",
+ total_blocks),
+ GNUNET_JSON_pack_string ("filter",
+ filter_s));
+ /* the pack helpers copy the strings */
+ GNUNET_free (prefix_s);
+ GNUNET_free (filter_s);
+ return TALER_MHD2_reply_json_steal (request,
+ resp,
+ MHD_HTTP_STATUS_OK);
+ }
+ }
+}
+
+
+/* end of sync-httpd2_get-backups-KEY-blocks-reconcile.c */
+\ No newline at end of file
diff --git a/src/sync/sync-httpd2_get-backups-KEY-blocks-reconcile.h b/src/sync/sync-httpd2_get-backups-KEY-blocks-reconcile.h
@@ -0,0 +1,48 @@
+/*
+ This file is part of TALER
+ Copyright (C) 2026 Taler Systems SA
+
+ TALER is free software; you can redistribute it and/or modify it under the
+ terms of the GNU Affero General Public License as published by the Free Software
+ Foundation; either version 3, or (at your option) any later version.
+
+ TALER is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details.
+
+ You should have received a copy of the GNU Affero General Public License along with
+ TALER; see the file COPYING. If not, see <http://www.gnu.org/licenses/>
+*/
+/**
+ * @file sync-httpd2_get-backups-KEY-blocks-reconcile.h
+ * @brief GET /backups/$KEY/blocks/reconcile — bloom filter over the
+ * account's blocks (DD 92)
+ * @author Iván Ávalos
+ */
+#ifndef SYNC_HTTPD2_GET_BACKUPS_KEY_BLOCKS_RECONCILE_H
+#define SYNC_HTTPD2_GET_BACKUPS_KEY_BLOCKS_RECONCILE_H
+
+#include <microhttpd2.h>
+#include "sync/sync_service.h"
+
+
+/**
+ * Handle GET /backups/$KEY/blocks/reconcile.
+ *
+ * @param request the MHD request to handle
+ * @param account_pub public key of the account
+ * @param args path segments (args[0]="reconcile")
+ * @param upload_size number of bytes being uploaded
+ * @param is_update whether the operation is an update
+ * @return MHD action
+ */
+const struct MHD_Action *
+SH_backup_blocks_reconcile_get (struct MHD_Request *request,
+ const struct SYNC_AccountPublicKeyP *account_pub
+ ,
+ const char *const args[],
+ uint_fast64_t upload_size,
+ bool is_update);
+
+
+#endif
+\ No newline at end of file
diff --git a/src/syncdb/meson.build b/src/syncdb/meson.build
@@ -6,7 +6,7 @@ sqldir = get_option('datadir') / 'sync' / 'sql'
# FIXME possibly provide this output in the tgz through dist script
run_command('make', '-f', 'Makefile.sql', 'all', check: true)
-sqlfiles = ['versioning.sql', 'procedures.sql', 'sync-0001.sql', 'drop.sql']
+sqlfiles = ['versioning.sql', 'procedures.sql', 'sync-0001.sql', 'sync-0002.sql', 'drop.sql']
install_data(sources: sqlfiles, install_dir: sqldir)
@@ -27,6 +27,7 @@ libsyncdb_SOURCES = [
'syncdb_update_block_TR.c',
'syncdb_lookup_account_TR.c',
'syncdb_lookup_block_range_TR.c',
+ 'syncdb_lookup_block_hashes_TR.c',
'syncdb_lookup_block_TR.c',
'syncdb_increment_lifetime_TR.c',
'syncdb_lookup_pending_payments_by_account.c',
diff --git a/src/syncdb/procedures.sql.in b/src/syncdb/procedures.sql.in
@@ -27,6 +27,7 @@ SET search_path TO sync;
#include "syncdb_delete_block_TR.sql"
#include "syncdb_update_block_TR.sql"
#include "syncdb_lookup_block_range_TR.sql"
+#include "syncdb_lookup_block_hashes_TR.sql"
#include "syncdb_lookup_block_TR.sql"
#include "syncdb_gc.sql"
diff --git a/src/syncdb/sync-0002.sql b/src/syncdb/sync-0002.sql
@@ -0,0 +1,36 @@
+--
+-- This file is part of TALER
+-- Copyright (C) 2026 Taler Systems SA
+--
+-- TALER is free software; you can redistribute it and/or modify it under the
+-- terms of the GNU General Public License as published by the Free Software
+-- Foundation; either version 3, or (at your option) any later version.
+--
+-- TALER is distributed in the hope that it will be useful, but WITHOUT ANY
+-- WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+-- A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+--
+-- You should have received a copy of the GNU General Public License along with
+-- TALER; see the file COPYING. If not, see <http://www.gnu.org/licenses/>
+--
+
+-- Everything in one big transaction
+BEGIN;
+
+-- Check patch versioning is in place.
+SELECT _v.register_patch('sync-0002', NULL, NULL);
+
+SET search_path TO sync;
+
+-- Return type of sync_do_lookup_block_hashes(), added for the
+-- reconcile (invertible bloom filter) mechanism (DD 92).
+CREATE TYPE sync_do_lookup_block_hashes_return_type
+ AS
+ (out_account_missing BOOLEAN
+ ,out_backup_empty BOOLEAN
+ ,nonce BYTEA
+ ,block_hash BYTEA
+ );
+
+-- Complete transaction
+COMMIT;
+\ No newline at end of file
diff --git a/src/syncdb/syncdb_lookup_block_hashes_TR.c b/src/syncdb/syncdb_lookup_block_hashes_TR.c
@@ -0,0 +1,176 @@
+/*
+ This file is part of TALER
+ (C) 2026 Taler Systems SA
+
+ TALER is free software; you can redistribute it and/or modify it under the
+ terms of the GNU Lesser General Public License as published by the Free Software
+ Foundation; either version 3, or (at your option) any later version.
+
+ TALER is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License along with
+ TALER; see the file COPYING. If not, see <http://www.gnu.org/licenses/>
+*/
+/**
+ * @file syncdb/syncdb_lookup_block_hashes_TR.c
+ * @brief lookup the hashes of all the blocks of an account
+ * @author Iván Ávalos
+ */
+#include "syncdb_pg.h"
+
+
+/**
+ * Closure for the hash iterator callback.
+ */
+struct HashIteratorContext
+{
+ /**
+ * Iterator function to call for every block.
+ */
+ SYNC_DB_BlockHashIterator it;
+
+ /**
+ * Closure for @e it.
+ */
+ void *it_cls;
+
+ /**
+ * Query status to return.
+ */
+ enum SYNC_DB_QueryStatus qs;
+
+ /**
+ * Number of block hashes returned.
+ */
+ uint32_t num_hashes;
+
+ /**
+ * True if the account does not exist.
+ */
+ bool out_account_missing;
+
+ /**
+ * True if the account has no blocks at all.
+ */
+ bool out_backup_empty;
+};
+
+
+/**
+ * Helper function for #SYNCDB_lookup_block_hashes_TR().
+ * To be called with the results of a SELECT statement
+ * that has returned @a num_results results.
+ *
+ * @param cls closure of type `struct HashIteratorContext *`
+ * @param result the postgres result
+ * @param num_results the number of results in @a result
+ */
+static void
+block_hashes_cb (void *cls,
+ PGresult *result,
+ unsigned int num_results)
+{
+ struct HashIteratorContext *hic = cls;
+
+ for (unsigned int i = 0; i < num_results; i++)
+ {
+ bool out_account_missing;
+ bool out_backup_empty;
+ struct SYNC_BlockNonce nonce;
+ struct GNUNET_HashCode block_hash;
+ struct GNUNET_PQ_ResultSpec rs[] = {
+ GNUNET_PQ_result_spec_bool ("out_account_missing",
+ &out_account_missing),
+ GNUNET_PQ_result_spec_bool ("out_backup_empty",
+ &out_backup_empty),
+ GNUNET_PQ_result_spec_auto_from_type ("nonce",
+ &nonce),
+ GNUNET_PQ_result_spec_auto_from_type ("block_hash",
+ &block_hash),
+ GNUNET_PQ_result_spec_end,
+ };
+
+ if (GNUNET_OK !=
+ GNUNET_PQ_extract_result (result,
+ rs,
+ i))
+ {
+ GNUNET_break (0);
+ hic->qs = SYNC_DB_SOFT_ERROR;
+ return;
+ }
+
+ hic->qs = i + 1;
+ hic->out_account_missing = out_account_missing;
+ hic->out_backup_empty = out_backup_empty;
+ if ( (! out_account_missing) &&
+ (! out_backup_empty) )
+ {
+ /* Count the block even in the counting pass (NULL iterator) */
+ hic->num_hashes++;
+ if (NULL != hic->it)
+ hic->it (hic->it_cls,
+ &nonce,
+ &block_hash);
+ }
+ GNUNET_PQ_cleanup_result (rs);
+ }
+}
+
+
+enum SYNC_DB_QueryStatus
+SYNCDB_lookup_block_hashes_TR (
+ const struct SYNC_AccountPublicKeyP *account_pub,
+ SYNC_DB_BlockHashIterator it,
+ void *it_cls)
+{
+ struct GNUNET_PQ_QueryParam params[] = {
+ GNUNET_PQ_query_param_auto_from_type (account_pub),
+ GNUNET_PQ_query_param_end,
+ };
+ struct HashIteratorContext hic = {
+ .it = it,
+ .it_cls = it_cls,
+ };
+ enum GNUNET_DB_QueryStatus qs;
+
+ SYNCDB_preflight ();
+ PREPARE ("blocks_select_hashes",
+ "SELECT"
+ " out_account_missing"
+ ",out_backup_empty"
+ ",nonce"
+ ",block_hash"
+ " FROM sync_do_lookup_block_hashes"
+ " ($1)");
+ qs = GNUNET_PQ_eval_prepared_multi_select (pg->conn,
+ "blocks_select_hashes",
+ params,
+ &block_hashes_cb,
+ &hic);
+ switch (qs)
+ {
+ case GNUNET_DB_STATUS_HARD_ERROR:
+ GNUNET_break (0);
+ return SYNC_DB_HARD_ERROR;
+ case GNUNET_DB_STATUS_SOFT_ERROR:
+ return SYNC_DB_SOFT_ERROR;
+ case GNUNET_DB_STATUS_SUCCESS_NO_RESULTS:
+ /* the stored procedure always returns a status row */
+ GNUNET_break (0);
+ return SYNC_DB_NO_RESULTS;
+ default:
+ break;
+ }
+ /* map the flags of the (single) status row to SYNC_DB codes */
+ if (hic.out_account_missing)
+ return SYNC_DB_PAYMENT_REQUIRED;
+ if (hic.out_backup_empty)
+ return SYNC_DB_NO_RESULTS;
+ return hic.num_hashes;
+}
+
+
+/* end of syncdb_lookup_block_hashes_TR.c */
+\ No newline at end of file
diff --git a/src/syncdb/syncdb_lookup_block_hashes_TR.sql b/src/syncdb/syncdb_lookup_block_hashes_TR.sql
@@ -0,0 +1,69 @@
+--
+-- This file is part of TALER
+-- Copyright (C) 2026 Taler Systems SA
+--
+-- TALER is free software; you can redistribute it and/or modify it under the
+-- terms of the GNU General Public License as published by the Free Software
+-- Foundation; either version 3, or (at your option) any later version.
+--
+-- TALER is distributed in the hope that it will be useful, but WITHOUT ANY
+-- WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+-- A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+--
+-- You should have received a copy of the GNU General Public License along with
+-- TALER; see the file COPYING. If not, see <http://www.gnu.org/licenses/>
+--
+
+DROP FUNCTION IF EXISTS sync_do_lookup_block_hashes;
+CREATE FUNCTION sync_do_lookup_block_hashes (
+ IN in_account_pub BYTEA)
+RETURNS SETOF sync_do_lookup_block_hashes_return_type
+LANGUAGE plpgsql
+AS $$
+DECLARE
+ my_first_block BYTEA;
+ r RECORD;
+BEGIN
+
+ -- Check if account exists
+ SELECT first_block
+ INTO my_first_block
+ FROM accounts
+ WHERE account_pub = in_account_pub;
+
+ IF NOT FOUND
+ THEN
+ RETURN NEXT (TRUE -- out_account_missing
+ ,FALSE
+ ,decode(repeat('00', 24), 'hex')
+ ,decode(repeat('00', 64), 'hex'));
+ RETURN;
+ END IF;
+
+ -- Check if backup is empty
+ IF my_first_block IS NULL
+ THEN
+ RETURN NEXT (FALSE
+ ,TRUE -- out_backup_empty
+ ,decode(repeat('00', 24), 'hex')
+ ,decode(repeat('00', 64), 'hex'));
+ RETURN;
+ END IF;
+
+ -- Stream the identities of all the blocks in the account's linked
+ -- list (the order does not matter, the caller builds an invertible
+ -- bloom filter over them).
+ FOR r IN
+ SELECT nonce
+ ,block_hash
+ FROM blocks
+ WHERE account_pub = in_account_pub
+ LOOP
+ RETURN NEXT (FALSE
+ ,FALSE
+ ,r.nonce
+ ,r.block_hash);
+ END LOOP;
+
+ RETURN;
+END $$;
+\ No newline at end of file
diff --git a/src/syncdb/test_sync_db.c b/src/syncdb/test_sync_db.c
@@ -111,6 +111,50 @@ block_it (void *cls,
/**
+ * Iterator used by the #SYNCDB_lookup_block_hashes_TR() tests,
+ * collecting the block identities it is called with.
+ */
+struct HashCollector
+{
+ /**
+ * Nonces collected so far.
+ */
+ struct SYNC_BlockNonce nonces[8];
+
+ /**
+ * Hashes collected so far.
+ */
+ struct GNUNET_HashCode hashes[8];
+
+ /**
+ * Number of entries collected.
+ */
+ unsigned int count;
+};
+
+
+/**
+ * Collect the block identities the iterator is called with.
+ *
+ * @param cls a `struct HashCollector *`
+ * @param nonce nonce identifying the block
+ * @param block_hash hash of the block data
+ */
+static void
+hash_it (void *cls,
+ const struct SYNC_BlockNonce *nonce,
+ const struct GNUNET_HashCode *block_hash)
+{
+ struct HashCollector *hc = cls;
+
+ GNUNET_assert (hc->count < 8);
+ hc->nonces[hc->count] = *nonce;
+ hc->hashes[hc->count] = *block_hash;
+ hc->count++;
+}
+
+
+/**
* Create a paid account, so that the SQL entry points do not reject
* it with #SYNC_DB_PAYMENT_REQUIRED.
*
@@ -486,6 +530,90 @@ run (void *cls)
NULL,
NULL));
}
+
+ /* --- Block hash lookup (reconcile) tests --- */
+ {
+ struct SYNC_AccountPublicKeyP unknown;
+ struct SYNC_AccountPublicKeyP lone;
+ struct SYNC_BlockNonce lone_nonce;
+ struct GNUNET_HashCode lone_hash;
+ char lone_data[] = "lone-block";
+ struct HashCollector hc;
+
+ /* An account nobody has heard of demands payment */
+ memset (&unknown, 9, sizeof (unknown));
+ FAILIF (SYNC_DB_PAYMENT_REQUIRED !=
+ SYNCDB_lookup_block_hashes_TR (&unknown,
+ NULL,
+ NULL));
+
+ /* A fresh, paid account with a single block delivers exactly
+ that block's hash */
+ memset (&lone, 16, sizeof (lone));
+ FAILIF (GNUNET_OK !=
+ activate_account (&lone,
+ "fake-order-hashes-lone"));
+ RND_BLK (&lone_nonce);
+ GNUNET_CRYPTO_hash (lone_data,
+ sizeof lone_data - 1,
+ &lone_hash);
+ FAILIF (SYNC_DB_ONE_RESULT !=
+ SYNCDB_append_block_TR (&lone,
+ &lone_nonce,
+ NULL,
+ &lone_hash,
+ sizeof lone_data - 1,
+ lone_data,
+ 0,
+ NULL,
+ NULL,
+ &fake_sig,
+ &empty_refs,
+ NULL,
+ NULL,
+ NULL));
+ memset (&hc, 0, sizeof (hc));
+ FAILIF (1 !=
+ SYNCDB_lookup_block_hashes_TR (&lone,
+ &hash_it,
+ &hc));
+ FAILIF (1 != hc.count);
+ FAILIF (0 != GNUNET_memcmp (&hc.hashes[0],
+ &lone_hash));
+ FAILIF (0 != GNUNET_memcmp (&hc.nonces[0],
+ &lone_nonce));
+
+ /* Counting pass with a NULL iterator */
+ FAILIF (1 !=
+ SYNCDB_lookup_block_hashes_TR (&lone,
+ NULL,
+ NULL));
+
+ /* The DLL account now holds blocks A and C (B was deleted, C
+ was updated), whose identities must both be delivered */
+ memset (&hc, 0, sizeof (hc));
+ FAILIF (2 !=
+ SYNCDB_lookup_block_hashes_TR (&account_pub,
+ &hash_it,
+ &hc));
+ FAILIF (2 != hc.count);
+ {
+ bool have_a = false;
+ bool have_c = false;
+
+ for (unsigned int i = 0; i < hc.count; i++)
+ {
+ if (0 == GNUNET_memcmp (&hc.hashes[i],
+ &hA))
+ have_a = true;
+ if (0 == GNUNET_memcmp (&hc.hashes[i],
+ &hC))
+ have_c = true;
+ }
+ FAILIF (! have_a);
+ FAILIF (! have_c);
+ }
+ }
}
/* --- Account status lookup --- */
diff --git a/src/testing/meson.build b/src/testing/meson.build
@@ -8,6 +8,7 @@ libsynctesting = library(
'testing_api_cmd_block_update.c',
'testing_api_cmd_block_delete.c',
'testing_api_cmd_block_list.c',
+ 'testing_api_cmd_block_reconcile.c',
'testing_api_cmd_object_upload.c',
'testing_api_cmd_object_fetch.c',
],
diff --git a/src/testing/test_sync_api.c b/src/testing/test_sync_api.c
@@ -139,6 +139,8 @@ run (void *cls,
struct SYNC_BlockNonce nonces[3];
/* Hashes of blocks A, C and D, in chain order. */
struct GNUNET_HashCode hashes[3];
+ /* Mixing salt used for the reconcile tests. */
+ uint32_t reconcile_prefix;
/* Nonce of a block that is never successfully uploaded. */
struct SYNC_BlockNonce nonce_stale;
/* Nonce that never exists on the server. */
@@ -177,6 +179,7 @@ run (void *cls,
GNUNET_CRYPTO_hash (data[i + 1],
strlen (data[i + 1]),
&hashes[i]);
+ reconcile_prefix = 0x01020304;
{
struct TALER_TESTING_Command commands[] = {
@@ -407,6 +410,102 @@ run (void *cls,
0,
NULL,
NULL),
+
+ /* ========== Reconcile (invertible bloom filter) tests ========== */
+
+ /* A wallet holding exactly the server's blocks decodes an empty
+ difference from the filter. */
+ SYNC_TESTING_cmd_block_reconcile ("reconcile-in-sync",
+ sync_url,
+ "upload-block-2",
+ MHD_HTTP_OK,
+ 2,
+ NULL,
+ 2,
+ nonces,
+ hashes,
+ 0,
+ NULL,
+ NULL,
+ 0,
+ NULL,
+ NULL),
+ /* With a fresh salt the filter still matches every block, and
+ the reply echoes the requested salt. */
+ SYNC_TESTING_cmd_block_reconcile ("reconcile-prefix",
+ sync_url,
+ "upload-block-2",
+ MHD_HTTP_OK,
+ 2,
+ &reconcile_prefix,
+ 2,
+ nonces,
+ hashes,
+ 0,
+ NULL,
+ NULL,
+ 0,
+ NULL,
+ NULL),
+ /* A wallet that still holds the deleted block D sees it as
+ stale (local-only); nothing is missing. */
+ SYNC_TESTING_cmd_block_reconcile ("reconcile-stale",
+ sync_url,
+ "upload-block-2",
+ MHD_HTTP_OK,
+ 2,
+ NULL,
+ 3,
+ nonces,
+ hashes,
+ 0,
+ NULL,
+ NULL,
+ 1,
+ &nonces[2],
+ &hashes[2]),
+ /* A wallet holding only block A enumerates block B as missing
+ (server-only). */
+ SYNC_TESTING_cmd_block_reconcile ("reconcile-missing",
+ sync_url,
+ "upload-block-2",
+ MHD_HTTP_OK,
+ 2,
+ NULL,
+ 1,
+ nonces,
+ hashes,
+ 1,
+ &nonces[1],
+ &hashes[1],
+ 0,
+ NULL,
+ NULL),
+
+ /* ========== Single block fetch tests ========== */
+
+ /* A block is fetchable by nonce through the list endpoint with
+ limit 1 and an inclusive start_nonce, with its payload and
+ signature intact. */
+ SYNC_TESTING_cmd_block_list ("fetch-block-B",
+ sync_url,
+ "upload-block-2",
+ 1,
+ &nonces[1],
+ MHD_HTTP_OK,
+ 1,
+ &nonces[1],
+ &hashes[1]),
+ /* A nonce that is not part of the linked list is not found. */
+ SYNC_TESTING_cmd_block_list ("fetch-block-unknown",
+ sync_url,
+ "upload-block-2",
+ 1,
+ &bogus_nonce,
+ MHD_HTTP_NOT_FOUND,
+ 0,
+ NULL,
+ NULL),
/* Final list confirms all is well */
SYNC_TESTING_cmd_block_list ("list-blocks-end",
sync_url,
diff --git a/src/testing/testing_api_cmd_block_reconcile.c b/src/testing/testing_api_cmd_block_reconcile.c
@@ -0,0 +1,514 @@
+/*
+ This file is part of SYNC
+ Copyright (C) 2026 Taler Systems SA
+
+ SYNC is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as
+ published by the Free Software Foundation; either version 3, or
+ (at your option) any later version.
+
+ SYNC is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public
+ License along with SYNC; see the file COPYING. If not, see
+ <http://www.gnu.org/licenses/>
+*/
+/**
+ * @file testing/testing_api_cmd_block_reconcile.c
+ * @brief command to fetch and verify the invertible bloom filter of an
+ * account from the sync backend service (DD 92)
+ * @author Iván Ávalos
+ */
+#include "platform.h"
+#include "sync/sync_service.h"
+#include "sync/sync_signatures.h"
+#include "sync/sync_ibf.h"
+#include "sync/sync_testing_lib.h"
+#include <taler/taler_util.h>
+#include <taler/taler_testing_lib.h>
+#include <gnunet/gnunet_curl_lib.h>
+
+
+/**
+ * Maximum number of entries in the local set and in the expected
+ * differences.
+ */
+#define MAX_RECONCILE_ENTRIES 256
+
+
+/**
+ * State for a "block reconcile" CMD.
+ */
+struct BlockReconcileState
+{
+
+ /**
+ * URL of the sync backend.
+ */
+ const char *sync_url;
+
+ /**
+ * Reference to a command that provides the account public key.
+ */
+ const char *account_reference;
+
+ /**
+ * Account public key to query.
+ */
+ struct SYNC_AccountPublicKeyP account_pub;
+
+ /**
+ * Optional mixing salt to request (NULL for none).
+ */
+ uint32_t *prefix;
+
+ /**
+ * Expected HTTP status code.
+ */
+ unsigned int http_status;
+
+ /**
+ * Expected number of blocks the filter must report.
+ */
+ uint32_t expected_total_blocks;
+
+ /**
+ * The interpreter state.
+ */
+ struct TALER_TESTING_Interpreter *is;
+
+ /**
+ * Handle for the library block reconcile operation.
+ */
+ struct SYNC_ReconcileOperation *ro;
+
+ /**
+ * Number of blocks the wallet holds locally.
+ */
+ unsigned int num_local;
+
+ /**
+ * Nonces of the locally held blocks (array of @e num_local).
+ */
+ struct SYNC_BlockNonce local_nonces[MAX_RECONCILE_ENTRIES];
+
+ /**
+ * Hashes of the locally held blocks (array of @e num_local).
+ */
+ struct GNUNET_HashCode local_hashes[MAX_RECONCILE_ENTRIES];
+
+ /**
+ * Number of blocks expected to be missing locally (server-only).
+ */
+ unsigned int num_missing;
+
+ /**
+ * Nonces of the blocks expected missing (array of @e num_missing).
+ */
+ struct SYNC_BlockNonce missing_nonces[MAX_RECONCILE_ENTRIES];
+
+ /**
+ * Hashes of the blocks expected missing (array of @e num_missing).
+ */
+ struct GNUNET_HashCode missing_hashes[MAX_RECONCILE_ENTRIES];
+
+ /**
+ * Number of blocks expected to be stale locally (local-only).
+ */
+ unsigned int num_stale;
+
+ /**
+ * Nonces of the blocks expected stale (array of @e num_stale).
+ */
+ struct SYNC_BlockNonce stale_nonces[MAX_RECONCILE_ENTRIES];
+
+ /**
+ * Hashes of the blocks expected stale (array of @e num_stale).
+ */
+ struct GNUNET_HashCode stale_hashes[MAX_RECONCILE_ENTRIES];
+
+};
+
+
+/**
+ * Look up a decoded element in the expected arrays.
+ *
+ * @param key element to find (nonce || hash)
+ * @param num number of entries in @a nonces and @a hashes
+ * @param nonces expected nonces
+ * @param hashes expected hashes
+ * @param[out] used set to true when found (for duplicate checks)
+ * @return #GNUNET_YES if found, #GNUNET_NO if not
+ */
+static enum GNUNET_GenericReturnValue
+match_expected (const struct SYNC_IBFKey *key,
+ unsigned int num,
+ const struct SYNC_BlockNonce *nonces,
+ const struct GNUNET_HashCode *hashes,
+ bool *used)
+{
+ for (unsigned int i = 0; i < num; i++)
+ {
+ if (used[i])
+ continue;
+ if ( (0 == memcmp (key->nonce,
+ &nonces[i],
+ sizeof (key->nonce))) &&
+ (0 == memcmp (key->hash,
+ &hashes[i],
+ sizeof (key->hash))) )
+ {
+ used[i] = true;
+ return GNUNET_YES;
+ }
+ }
+ return GNUNET_NO;
+}
+
+
+/**
+ * Function called when we're done processing the block reconcile.
+ *
+ * @param cls the `struct BlockReconcileState`
+ * @param rd details about the reconcile operation
+ */
+static void
+handle_reconcile_finished (void *cls,
+ const struct SYNC_ReconcileDetails *rd)
+{
+ struct BlockReconcileState *brs = cls;
+ struct SYNC_IBF *server_ibf;
+ struct SYNC_IBF *local_ibf;
+ bool used_missing[MAX_RECONCILE_ENTRIES] = { false };
+ bool used_stale[MAX_RECONCILE_ENTRIES] = { false };
+
+ brs->ro = NULL;
+ if (rd->http_status != brs->http_status)
+ {
+ TALER_TESTING_unexpected_status (brs->is,
+ rd->http_status,
+ brs->http_status);
+ return;
+ }
+ if (MHD_HTTP_OK != rd->http_status)
+ {
+ /* error case: nothing more to check */
+ TALER_TESTING_interpreter_next (brs->is);
+ return;
+ }
+
+ if (rd->total_blocks != brs->expected_total_blocks)
+ {
+ GNUNET_break_op (0);
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "Expected %u blocks in reconcile, got %u\n",
+ (unsigned int) brs->expected_total_blocks,
+ (unsigned int) rd->total_blocks);
+ TALER_TESTING_interpreter_fail (brs->is);
+ return;
+ }
+ if ( (NULL != brs->prefix) &&
+ (*brs->prefix != rd->prefix) )
+ {
+ GNUNET_break_op (0);
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "Reconcile used prefix %u, expected %u\n",
+ (unsigned int) rd->prefix,
+ (unsigned int) *brs->prefix);
+ TALER_TESTING_interpreter_fail (brs->is);
+ return;
+ }
+
+ server_ibf = SYNC_ibf_deserialize (rd->data,
+ rd->bucket_count,
+ rd->k,
+ rd->prefix);
+ if (NULL == server_ibf)
+ {
+ GNUNET_break_op (0);
+ TALER_TESTING_interpreter_fail (brs->is);
+ return;
+ }
+ /* Rebuild the wallet's side of the reconciliation, as it would: the
+ local filter over the blocks it holds, subtracted from the
+ server's, enumerates exactly the difference. */
+ local_ibf = SYNC_ibf_create (rd->bucket_count,
+ rd->k,
+ rd->prefix);
+ if (NULL == local_ibf)
+ {
+ GNUNET_break_op (0);
+ SYNC_ibf_destroy (server_ibf);
+ TALER_TESTING_interpreter_fail (brs->is);
+ return;
+ }
+ for (unsigned int i = 0; i < brs->num_local; i++)
+ {
+ struct SYNC_IBFKey key;
+
+ memcpy (key.nonce,
+ &brs->local_nonces[i],
+ sizeof (key.nonce));
+ memcpy (key.hash,
+ &brs->local_hashes[i],
+ sizeof (key.hash));
+ SYNC_ibf_insert (local_ibf,
+ &key);
+ }
+ SYNC_ibf_subtract (server_ibf,
+ local_ibf);
+ {
+ bool mismatch = false;
+ unsigned int got_missing = 0;
+ unsigned int got_stale = 0;
+
+ for (;;)
+ {
+ enum GNUNET_GenericReturnValue res;
+ struct SYNC_IBFKey key;
+ int16_t side;
+
+ res = SYNC_ibf_decode (server_ibf,
+ &side,
+ &key);
+ if (GNUNET_YES != res)
+ {
+ if (GNUNET_NO != res)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "Reconcile filter cannot be decoded (difference"
+ " too large for its size)\n");
+ mismatch = true;
+ }
+ break;
+ }
+ if (1 == side)
+ {
+ if (GNUNET_YES !=
+ match_expected (&key,
+ brs->num_missing,
+ brs->missing_nonces,
+ brs->missing_hashes,
+ used_missing))
+ {
+ GNUNET_break_op (0);
+ mismatch = true;
+ break;
+ }
+ got_missing++;
+ }
+ else
+ {
+ if (GNUNET_YES !=
+ match_expected (&key,
+ brs->num_stale,
+ brs->stale_nonces,
+ brs->stale_hashes,
+ used_stale))
+ {
+ GNUNET_break_op (0);
+ mismatch = true;
+ break;
+ }
+ got_stale++;
+ }
+ }
+ if ( (! mismatch) &&
+ (got_missing != brs->num_missing) )
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "Reconcile decoded %u missing blocks, expected %u\n",
+ got_missing,
+ brs->num_missing);
+ mismatch = true;
+ }
+ if ( (! mismatch) &&
+ (got_stale != brs->num_stale) )
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+ "Reconcile decoded %u stale blocks, expected %u\n",
+ got_stale,
+ brs->num_stale);
+ mismatch = true;
+ }
+ if (mismatch)
+ {
+ GNUNET_break_op (0);
+ TALER_TESTING_interpreter_fail (brs->is);
+ SYNC_ibf_destroy (local_ibf);
+ SYNC_ibf_destroy (server_ibf);
+ return;
+ }
+ }
+ SYNC_ibf_destroy (local_ibf);
+ SYNC_ibf_destroy (server_ibf);
+ TALER_TESTING_interpreter_next (brs->is);
+}
+
+
+/**
+ * Run a "block reconcile" CMD.
+ *
+ * @param cls closure.
+ * @param cmd command currently being run.
+ * @param is interpreter state.
+ */
+static void
+reconcile_run (void *cls,
+ const struct TALER_TESTING_Command *cmd,
+ struct TALER_TESTING_Interpreter *is)
+{
+ struct BlockReconcileState *brs = cls;
+
+ (void) cmd;
+ brs->is = is;
+
+ if (NULL != brs->account_reference)
+ {
+ const struct TALER_TESTING_Command *ref;
+
+ ref = TALER_TESTING_interpreter_lookup_command (is,
+ brs->account_reference);
+ if (NULL == ref)
+ {
+ GNUNET_break (0);
+ goto fail;
+ }
+ {
+ const struct SYNC_AccountPublicKeyP *pub;
+
+ if (GNUNET_OK !=
+ TALER_TESTING_get_trait_sync_account_pub (ref,
+ &pub))
+ goto fail;
+ brs->account_pub = *pub;
+ }
+ }
+ else
+ goto fail;
+
+ brs->ro = SYNC_block_reconcile (
+ TALER_TESTING_interpreter_get_context (is),
+ brs->sync_url,
+ &brs->account_pub,
+ brs->prefix,
+ &handle_reconcile_finished,
+ brs);
+ if (NULL == brs->ro)
+ goto fail;
+
+ return;
+
+fail:
+ GNUNET_break (0);
+ TALER_TESTING_interpreter_fail (is);
+}
+
+
+/**
+ * Free the state of a "block reconcile" CMD, and possibly
+ * cancel it if it did not complete.
+ *
+ * @param cls closure.
+ * @param cmd command being freed.
+ */
+static void
+reconcile_cleanup (void *cls,
+ const struct TALER_TESTING_Command *cmd)
+{
+ struct BlockReconcileState *brs = cls;
+
+ if (NULL != brs->ro)
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
+ "Command '%s' did not complete (block reconcile)\n",
+ cmd->label);
+ SYNC_block_reconcile_cancel (brs->ro);
+ brs->ro = NULL;
+ }
+ GNUNET_free (brs->prefix);
+ GNUNET_free (brs);
+}
+
+
+struct TALER_TESTING_Command
+SYNC_TESTING_cmd_block_reconcile (const char *label,
+ const char *sync_url,
+ const char *account_reference,
+ unsigned int http_status,
+ uint32_t expected_total_blocks,
+ const uint32_t *prefix,
+ unsigned int num_local,
+ const struct SYNC_BlockNonce *local_nonces,
+ const struct GNUNET_HashCode *local_hashes,
+ unsigned int num_missing,
+ const struct SYNC_BlockNonce *missing_nonces,
+ const struct GNUNET_HashCode *missing_hashes,
+ unsigned int num_stale,
+ const struct SYNC_BlockNonce *stale_nonces,
+ const struct GNUNET_HashCode *stale_hashes)
+{
+ struct BlockReconcileState *brs;
+
+ GNUNET_assert (num_local <= MAX_RECONCILE_ENTRIES);
+ GNUNET_assert (num_missing <= MAX_RECONCILE_ENTRIES);
+ GNUNET_assert (num_stale <= MAX_RECONCILE_ENTRIES);
+ brs = GNUNET_new (struct BlockReconcileState);
+ brs->sync_url = sync_url;
+ brs->account_reference = account_reference;
+ brs->http_status = http_status;
+ brs->expected_total_blocks = expected_total_blocks;
+ if (NULL != prefix)
+ {
+ brs->prefix = GNUNET_new (uint32_t);
+ *brs->prefix = *prefix;
+ }
+ else
+ brs->prefix = NULL;
+ brs->num_local = num_local;
+ if (0 < num_local)
+ {
+ GNUNET_memcpy (brs->local_nonces,
+ local_nonces,
+ num_local * sizeof (struct SYNC_BlockNonce));
+ GNUNET_memcpy (brs->local_hashes,
+ local_hashes,
+ num_local * sizeof (struct GNUNET_HashCode));
+ }
+ brs->num_missing = num_missing;
+ if (0 < num_missing)
+ {
+ GNUNET_memcpy (brs->missing_nonces,
+ missing_nonces,
+ num_missing * sizeof (struct SYNC_BlockNonce));
+ GNUNET_memcpy (brs->missing_hashes,
+ missing_hashes,
+ num_missing * sizeof (struct GNUNET_HashCode));
+ }
+ brs->num_stale = num_stale;
+ if (0 < num_stale)
+ {
+ GNUNET_memcpy (brs->stale_nonces,
+ stale_nonces,
+ num_stale * sizeof (struct SYNC_BlockNonce));
+ GNUNET_memcpy (brs->stale_hashes,
+ stale_hashes,
+ num_stale * sizeof (struct GNUNET_HashCode));
+ }
+ {
+ struct TALER_TESTING_Command cmd = {
+ .cls = brs,
+ .label = label,
+ .run = &reconcile_run,
+ .cleanup = &reconcile_cleanup
+ };
+
+ return cmd;
+ }
+}
+
+
+/* end of testing_api_cmd_block_reconcile.c */
+\ No newline at end of file
diff --git a/src/util/meson.build b/src/util/meson.build
@@ -10,7 +10,7 @@ configure_file(
libsyncutil = library(
'syncutil',
- ['os_installation.c', 'sync_signatures.c', 'sync_block.c', 'sync_object.c'],
+ ['os_installation.c', 'sync_signatures.c', 'sync_block.c', 'sync_object.c', 'sync_ibf.c'],
soversion: solibversions['libsyncutil']['soversion'],
version: solibversions['libsyncutil']['soversion'],
install_rpath: rpath_option,
@@ -66,3 +66,27 @@ test(
)
+test_sync_ibf = executable(
+ 'test_sync_ibf',
+ ['test_sync_ibf.c'],
+ install_rpath: rpath_option,
+ dependencies: [
+ libsyncutil_dep,
+ talerutil_dep,
+ gnunetutil_dep,
+ gnunetjson_dep,
+ json_dep,
+ ],
+ include_directories: [incdir, configuration_inc],
+ install: false,
+)
+# Not in 'installcheck', which the default test setup excludes: this
+# test needs neither an installed tree nor a database.
+test(
+ 'test_sync_ibf',
+ test_sync_ibf,
+ workdir: meson.current_build_dir(),
+ suite: ['util'],
+)
+
+
diff --git a/src/util/sync_block.c b/src/util/sync_block.c
@@ -40,6 +40,8 @@ SYNC_block_entry_parse (
json_t *input,
struct SYNC_BlockListEntry *entry)
{
+ bool missing_prev;
+ bool missing_next;
struct GNUNET_JSON_Specification espec[] = {
GNUNET_JSON_spec_fixed_auto ("nonce",
&entry->nonce),
@@ -51,11 +53,11 @@ SYNC_block_entry_parse (
GNUNET_JSON_spec_mark_optional (
GNUNET_JSON_spec_fixed_auto ("prev_nonce",
&entry->prev_nonce),
- &entry->have_prev_nonce),
+ &missing_prev),
GNUNET_JSON_spec_mark_optional (
GNUNET_JSON_spec_fixed_auto ("next_nonce",
&entry->next_nonce),
- &entry->have_next_nonce),
+ &missing_next),
GNUNET_JSON_spec_fixed_auto ("upload_sig",
&entry->upload_sig),
GNUNET_JSON_spec_fixed_auto ("old_hash",
@@ -80,6 +82,10 @@ SYNC_block_entry_parse (
ename);
return GNUNET_SYSERR;
}
+ /* The optional-field tracking flag reports whether the field is
+ *missing*; the entry records the inverse. */
+ entry->have_prev_nonce = ! missing_prev;
+ entry->have_next_nonce = ! missing_next;
return GNUNET_OK;
}
diff --git a/src/util/sync_ibf.c b/src/util/sync_ibf.c
@@ -0,0 +1,543 @@
+/*
+ This file is part of TALER
+ Copyright (C) 2026 Taler Systems SA
+
+ TALER is free software; you can redistribute it and/or modify it under the
+ terms of the GNU Affero General Public License as published by the Free Software
+ Foundation; either version 3, or (at your option) any later version.
+
+ TALER is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details.
+
+ You should have received a copy of the GNU Affero General Public License along with
+ TALER; see the file COPYING. If not, see <http://www.gnu.org/licenses/>
+*/
+/**
+ * @file util/sync_ibf.c
+ * @brief invertible bloom filter for backup reconciliation (DD 92)
+ * @author Iván Ávalos
+ */
+
+/**
+ * The filter is a set of @a size buckets, each holding:
+ *
+ * +--------------------------+
+ * | Counter (2 byte) |
+ * +--------------------------+
+ * | Key sum (88 byte) | XOR of the elements' keys
+ * +--------------------------+
+ * | Key hash sum (8 byte) | XOR of the elements' key hashes
+ * +--------------------------+
+ *
+ * Testing membership is not possible (unlike a plain bloom filter),
+ * but the filter is invertible: subtracting the filters of two sets
+ * yields the filter of their symmetric difference, and peeling pure
+ * buckets decodes the differing elements one by one. This is what
+ * makes targeted pulls possible: given the server's filter and its
+ * own, a wallet can enumerate exactly the blocks that were added,
+ * rewritten or deleted since it last looked.
+ *
+ * Bucket indices derive from successive 32-bit words of the SHA-512
+ * over element + mixing prefix, re-hashing when the words run out
+ * (as in GNUnet's bloom filters); duplicate indices are skipped, as
+ * in GNUnet's invertible-bloom-filter implementation (ibf.c in the
+ * SET service).
+ */
+#include "platform.h"
+#include <gnunet/gnunet_util_lib.h>
+#include "sync/sync_ibf.h"
+
+
+/**
+ * The filter.
+ */
+struct SYNC_IBF
+{
+ /**
+ * Number of buckets.
+ */
+ uint32_t size;
+
+ /**
+ * Number of hash functions per element.
+ */
+ unsigned int hash_num;
+
+ /**
+ * Mixing salt hashed with every element.
+ */
+ uint32_t prefix;
+
+ /**
+ * Per-bucket counters (number of insertions).
+ */
+ int16_t *count;
+
+ /**
+ * Per-bucket XOR sums of the element keys.
+ */
+ unsigned char *key_sum;
+
+ /**
+ * Per-bucket XOR sums of the element key hashes.
+ */
+ unsigned char *key_hash_sum;
+};
+
+
+/**
+ * Stream of 32-bit words over a hash chain: the words of the mingled
+ * hash, followed by the words of its hash, and so on, enough for any
+ * number of distinct bucket indices.
+ */
+struct WordStream
+{
+ /**
+ * Current hash of the chain.
+ */
+ unsigned char hash[64];
+
+ /**
+ * Next word to read from @e hash.
+ */
+ unsigned int slot;
+};
+
+
+/**
+ * Start the word stream over SHA-512(element || prefix).
+ *
+ * @param ws stream to initialize
+ * @param key element to hash
+ * @param prefix mixing salt (network byte order value)
+ */
+static void
+ws_init (struct WordStream *ws,
+ const struct SYNC_IBFKey *key,
+ uint32_t prefix)
+{
+ unsigned char input[SYNC_IBF_KEY_SIZE + 4];
+ uint32_t p = htonl (prefix);
+
+ memcpy (input,
+ key,
+ SYNC_IBF_KEY_SIZE);
+ memcpy (input + SYNC_IBF_KEY_SIZE,
+ &p,
+ sizeof (p));
+ GNUNET_CRYPTO_hash (input,
+ sizeof (input),
+ (struct GNUNET_HashCode *) ws->hash);
+ ws->slot = 0;
+}
+
+
+/**
+ * Read the next word of the stream.
+ *
+ * @param ws stream to read from
+ * @return next 32-bit word, in host byte order
+ */
+static uint32_t
+ws_next (struct WordStream *ws)
+{
+ uint32_t w;
+
+ if (ws->slot >= (sizeof (ws->hash) / sizeof (uint32_t)))
+ {
+ GNUNET_CRYPTO_hash (ws->hash,
+ sizeof (ws->hash),
+ (struct GNUNET_HashCode *) ws->hash);
+ ws->slot = 0;
+ }
+ memcpy (&w,
+ ws->hash + ws->slot * sizeof (w),
+ sizeof (w));
+ ws->slot++;
+ return ntohl (w);
+}
+
+
+/**
+ * Store the bucket indices of an element in @a dst, one per hash
+ * function, skipping duplicates.
+ *
+ * @param ibf filter the element maps into (for size and hash_num)
+ * @param key element
+ * @param dst array of @a hash_num bucket indices
+ */
+static void
+ibf_get_indices (const struct SYNC_IBF *ibf,
+ const struct SYNC_IBFKey *key,
+ int *dst)
+{
+ struct WordStream ws;
+ uint32_t filled = 0;
+
+ ws_init (&ws,
+ key,
+ ibf->prefix);
+ while (filled < ibf->hash_num)
+ {
+ uint32_t bucket = ws_next (&ws) % ibf->size;
+ bool dup = false;
+
+ for (uint32_t j = 0; j < filled; j++)
+ {
+ if (dst[j] == (int) bucket)
+ {
+ dup = true;
+ break;
+ }
+ }
+ if (! dup)
+ dst[filled++] = bucket;
+ }
+}
+
+
+/**
+ * Compute the key hash of an element: the first 8 bytes of SHA-512
+ * over the key.
+ *
+ * @param key element
+ * @param[out] kh where to store the key hash
+ */
+static void
+ibf_key_hash (const struct SYNC_IBFKey *key,
+ unsigned char kh[SYNC_IBF_KEY_HASH_SIZE])
+{
+ struct GNUNET_HashCode h;
+
+ GNUNET_CRYPTO_hash (key,
+ SYNC_IBF_KEY_SIZE,
+ &h);
+ memcpy (kh,
+ &h,
+ SYNC_IBF_KEY_HASH_SIZE);
+}
+
+
+/**
+ * XOR @a size bytes of @a src into @a dst.
+ */
+static void
+xor_into (unsigned char *dst,
+ const unsigned char *src,
+ size_t size)
+{
+ for (size_t i = 0; i < size; i++)
+ dst[i] ^= src[i];
+}
+
+
+/**
+ * Insert an element with sign @a side (+1 insert, -1 remove): the
+ * counterpart of inserting it on the opposite side peels it out.
+ *
+ * @param ibf filter to manipulate
+ * @param key element
+ * @param buckets its bucket indices
+ * @param side +1 or -1
+ */
+static void
+ibf_insert_into (struct SYNC_IBF *ibf,
+ const struct SYNC_IBFKey *key,
+ const int *buckets,
+ int16_t side)
+{
+ unsigned char kh[SYNC_IBF_KEY_HASH_SIZE];
+
+ ibf_key_hash (key,
+ kh);
+ for (unsigned int i = 0; i < ibf->hash_num; i++)
+ {
+ const int bucket = buckets[i];
+
+ ibf->count[bucket] += side;
+ xor_into (ibf->key_sum + ((size_t) bucket) * SYNC_IBF_KEY_SIZE,
+ (const unsigned char *) key,
+ SYNC_IBF_KEY_SIZE);
+ xor_into (ibf->key_hash_sum + ((size_t) bucket) * SYNC_IBF_KEY_HASH_SIZE,
+ kh,
+ SYNC_IBF_KEY_HASH_SIZE);
+ }
+}
+
+
+uint32_t
+SYNC_ibf_compute_bucket_count (uint32_t block_count)
+{
+ uint32_t size = SYNC_IBF_MIN_BUCKETS;
+
+ if (block_count > SYNC_IBF_MAX_BUCKETS)
+ return SYNC_IBF_MAX_BUCKETS;
+ while ( (size < SYNC_IBF_MAX_BUCKETS) &&
+ (size < block_count) )
+ size *= 2;
+ return size;
+}
+
+
+struct SYNC_IBF *
+SYNC_ibf_create (uint32_t bucket_count,
+ unsigned int hash_num,
+ uint32_t prefix)
+{
+ struct SYNC_IBF *ibf;
+
+ if ( (0 == bucket_count) ||
+ (0 == hash_num) )
+ return NULL;
+ ibf = GNUNET_new (struct SYNC_IBF);
+ ibf->size = bucket_count;
+ ibf->hash_num = hash_num;
+ ibf->prefix = prefix;
+ ibf->count = GNUNET_malloc (bucket_count * sizeof (int16_t));
+ ibf->key_sum = GNUNET_malloc ((size_t) bucket_count * SYNC_IBF_KEY_SIZE);
+ ibf->key_hash_sum = GNUNET_malloc ((size_t) bucket_count
+ * SYNC_IBF_KEY_HASH_SIZE);
+ return ibf;
+}
+
+
+struct SYNC_IBF *
+SYNC_ibf_deserialize (const void *data,
+ uint32_t bucket_count,
+ unsigned int hash_num,
+ uint32_t prefix)
+{
+ struct SYNC_IBF *ibf;
+
+ if ( (NULL == data) ||
+ (0 == bucket_count) ||
+ (0 == hash_num) )
+ return NULL;
+ ibf = SYNC_ibf_create (bucket_count,
+ hash_num,
+ prefix);
+ if (NULL == ibf)
+ return NULL;
+ for (uint32_t i = 0; i < bucket_count; i++)
+ {
+ const unsigned char *b = ((const unsigned char *) data)
+ + ((size_t) i) * SYNC_IBF_BUCKET_SIZE;
+
+ memcpy (&ibf->count[i],
+ b,
+ sizeof (int16_t));
+ ibf->count[i] = ntohs (ibf->count[i]);
+ memcpy (ibf->key_sum + ((size_t) i) * SYNC_IBF_KEY_SIZE,
+ b + 2,
+ SYNC_IBF_KEY_SIZE);
+ memcpy (ibf->key_hash_sum + ((size_t) i) * SYNC_IBF_KEY_HASH_SIZE,
+ b + 2 + SYNC_IBF_KEY_SIZE,
+ SYNC_IBF_KEY_HASH_SIZE);
+ }
+ return ibf;
+}
+
+
+size_t
+SYNC_ibf_get_serialized_size (const struct SYNC_IBF *ibf)
+{
+ if (NULL == ibf)
+ return 0;
+ return ((size_t) ibf->size) * SYNC_IBF_BUCKET_SIZE;
+}
+
+
+void
+SYNC_ibf_serialize (const struct SYNC_IBF *ibf,
+ void *data)
+{
+ for (uint32_t i = 0; i < ibf->size; i++)
+ {
+ unsigned char *b = ((unsigned char *) data)
+ + ((size_t) i) * SYNC_IBF_BUCKET_SIZE;
+ int16_t count = htons (ibf->count[i]);
+
+ memcpy (b,
+ &count,
+ sizeof (count));
+ memcpy (b + 2,
+ ibf->key_sum + ((size_t) i) * SYNC_IBF_KEY_SIZE,
+ SYNC_IBF_KEY_SIZE);
+ memcpy (b + 2 + SYNC_IBF_KEY_SIZE,
+ ibf->key_hash_sum + ((size_t) i) * SYNC_IBF_KEY_HASH_SIZE,
+ SYNC_IBF_KEY_HASH_SIZE);
+ }
+}
+
+
+void
+SYNC_ibf_destroy (struct SYNC_IBF *ibf)
+{
+ if (NULL == ibf)
+ return;
+ GNUNET_free (ibf->key_hash_sum);
+ GNUNET_free (ibf->key_sum);
+ GNUNET_free (ibf->count);
+ GNUNET_free (ibf);
+}
+
+
+void
+SYNC_ibf_insert (struct SYNC_IBF *ibf,
+ const struct SYNC_IBFKey *key)
+{
+ int buckets[ibf->hash_num];
+
+ GNUNET_assert (ibf->hash_num <= ibf->size);
+ ibf_get_indices (ibf,
+ key,
+ buckets);
+ ibf_insert_into (ibf,
+ key,
+ buckets,
+ 1);
+}
+
+
+void
+SYNC_ibf_remove (struct SYNC_IBF *ibf,
+ const struct SYNC_IBFKey *key)
+{
+ int buckets[ibf->hash_num];
+
+ GNUNET_assert (ibf->hash_num <= ibf->size);
+ ibf_get_indices (ibf,
+ key,
+ buckets);
+ ibf_insert_into (ibf,
+ key,
+ buckets,
+ -1);
+}
+
+
+void
+SYNC_ibf_subtract (struct SYNC_IBF *ibf1,
+ const struct SYNC_IBF *ibf2)
+{
+ GNUNET_assert (ibf1->size == ibf2->size);
+ GNUNET_assert (ibf1->hash_num == ibf2->hash_num);
+ for (uint32_t i = 0; i < ibf1->size; i++)
+ {
+ ibf1->count[i] -= ibf2->count[i];
+ xor_into (ibf1->key_sum + ((size_t) i) * SYNC_IBF_KEY_SIZE,
+ ibf2->key_sum + ((size_t) i) * SYNC_IBF_KEY_SIZE,
+ SYNC_IBF_KEY_SIZE);
+ xor_into (ibf1->key_hash_sum
+ + ((size_t) i) * SYNC_IBF_KEY_HASH_SIZE,
+ ibf2->key_hash_sum
+ + ((size_t) i) * SYNC_IBF_KEY_HASH_SIZE,
+ SYNC_IBF_KEY_HASH_SIZE);
+ }
+}
+
+
+/**
+ * Test if the filter is empty, i.e. all counts and sums are zero.
+ *
+ * @param ibf filter to test
+ * @return #GNUNET_YES if empty
+ */
+static int
+ibf_is_empty (const struct SYNC_IBF *ibf)
+{
+ for (uint32_t i = 0; i < ibf->size; i++)
+ {
+ if (0 != ibf->count[i])
+ return GNUNET_NO;
+ for (unsigned int j = 0; j < SYNC_IBF_KEY_HASH_SIZE; j++)
+ if (0 != ibf->key_hash_sum[((size_t) i) * SYNC_IBF_KEY_HASH_SIZE + j])
+ return GNUNET_NO;
+ for (unsigned int j = 0; j < SYNC_IBF_KEY_SIZE; j++)
+ if (0 != ibf->key_sum[((size_t) i) * SYNC_IBF_KEY_SIZE + j])
+ return GNUNET_NO;
+ }
+ return GNUNET_YES;
+}
+
+
+enum GNUNET_GenericReturnValue
+SYNC_ibf_decode (struct SYNC_IBF *ibf,
+ int16_t *ret_side,
+ struct SYNC_IBFKey *ret_key)
+{
+ for (uint32_t i = 0; i < ibf->size; i++)
+ {
+ struct SYNC_IBFKey peeled;
+ unsigned char kh[SYNC_IBF_KEY_HASH_SIZE];
+ int buckets[ibf->hash_num];
+
+ /* only pure buckets can be decoded */
+ if ( (1 != ibf->count[i]) &&
+ (-1 != ibf->count[i]) )
+ continue;
+
+ /* the key sum of a pure bucket is the key: work on a copy, since
+ peeling XORs it back out of the bucket this key came from */
+ memcpy (&peeled,
+ ibf->key_sum + ((size_t) i) * SYNC_IBF_KEY_SIZE,
+ SYNC_IBF_KEY_SIZE);
+
+ /* check the key's hash against the bucket's hash sum */
+ ibf_key_hash (&peeled,
+ kh);
+ {
+ bool kh_ok = true;
+
+ for (unsigned int j = 0; j < SYNC_IBF_KEY_HASH_SIZE; j++)
+ if (kh[j] !=
+ ibf->key_hash_sum[((size_t) i) * SYNC_IBF_KEY_HASH_SIZE + j])
+ {
+ kh_ok = false;
+ break;
+ }
+ if (! kh_ok)
+ continue;
+ }
+
+ /* the key must map to this bucket itself */
+ ibf_get_indices (ibf,
+ &peeled,
+ buckets);
+ {
+ bool hit = false;
+
+ for (unsigned int j = 0; j < ibf->hash_num; j++)
+ {
+ if (buckets[j] == (int) i)
+ {
+ hit = true;
+ break;
+ }
+ }
+ if (! hit)
+ continue;
+ }
+
+ if (NULL != ret_side)
+ *ret_side = ibf->count[i];
+ if (NULL != ret_key)
+ *ret_key = peeled;
+
+ /* insert on the opposite side, peeling the element out */
+ ibf_insert_into (ibf,
+ &peeled,
+ buckets,
+ -ibf->count[i]);
+
+ return GNUNET_YES;
+ }
+
+ if (GNUNET_YES == ibf_is_empty (ibf))
+ return GNUNET_NO;
+ return GNUNET_SYSERR;
+}
+
+
+/* end of sync_ibf.c */
+\ No newline at end of file
diff --git a/src/util/test_sync_ibf.c b/src/util/test_sync_ibf.c
@@ -0,0 +1,283 @@
+/*
+ This file is part of TALER
+ Copyright (C) 2026 Taler Systems SA
+
+ TALER is free software; you can redistribute it and/or modify it under the
+ terms of the GNU General Public License as published by the Free Software
+ Foundation; either version 3, or (at your option) any later version.
+
+ TALER is distributed in the hope that it will be useful, but WITHOUT ANY
+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+ A PARTICULAR PURPOSE. See the GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License along with
+ TALER; see the file COPYING. If not, see <http://www.gnu.org/licenses/>
+*/
+/**
+ * @file util/test_sync_ibf.c
+ * @brief tests for the sync invertible bloom filter (DD 92)
+ * @author Iván Ávalos
+ */
+#include "platform.h"
+#include <gnunet/gnunet_util_lib.h>
+#include "sync/sync_ibf.h"
+
+
+#define FAILIF(cond) \
+ do { \
+ if (! (cond)) break; \
+ GNUNET_break (0); \
+ return 1; \
+ } while (0)
+
+
+/**
+ * Deterministic element: nonce and hash filled with distinct bytes
+ * derived from @a i.
+ *
+ * @param i element number
+ * @param[out] key set to the element
+ */
+static void
+key_of (unsigned int i,
+ struct SYNC_IBFKey *key)
+{
+ memset (key,
+ i + 1,
+ sizeof (*key));
+ key->nonce[0] = (unsigned char) i;
+ key->hash[0] = (unsigned char) (i >> 8);
+}
+
+
+/**
+ * Insert and remove leave the filter empty again.
+ *
+ * @return 0 on success
+ */
+static int
+test_insert_remove (void)
+{
+ struct SYNC_IBF *ibf;
+ struct SYNC_IBFKey key;
+ size_t size;
+ void *data;
+
+ ibf = SYNC_ibf_create (SYNC_IBF_MIN_BUCKETS,
+ SYNC_IBF_HASH_NUM,
+ 0);
+ FAILIF (NULL == ibf);
+ for (unsigned int i = 0; i < 100; i++)
+ {
+ key_of (i,
+ &key);
+ SYNC_ibf_insert (ibf,
+ &key);
+ }
+ for (unsigned int i = 0; i < 100; i++)
+ {
+ key_of (i,
+ &key);
+ SYNC_ibf_remove (ibf,
+ &key);
+ }
+ size = SYNC_ibf_get_serialized_size (ibf);
+ data = GNUNET_malloc (size);
+ SYNC_ibf_serialize (ibf,
+ data);
+ for (size_t i = 0; i < size; i++)
+ if (0 != ((const unsigned char *) data)[i])
+ {
+ GNUNET_break (0);
+ GNUNET_free (data);
+ SYNC_ibf_destroy (ibf);
+ return 1;
+ }
+ GNUNET_free (data);
+ SYNC_ibf_destroy (ibf);
+ return 0;
+}
+
+
+/**
+ * The symmetric difference of two filters decodes to exactly the
+ * differing elements, with the correct side.
+ *
+ * Sets: A = {0..9} union {20..29}, B = {10..19} union {20..29}.
+ * After subtracting B from A, the difference holds 0..9 with side +1
+ * and 10..19 with side -1; 20..29 cancel out.
+ *
+ * @return 0 on success
+ */
+static int
+test_decode_difference (void)
+{
+ struct SYNC_IBF *ibf_a = SYNC_ibf_create (SYNC_IBF_MIN_BUCKETS,
+ SYNC_IBF_HASH_NUM,
+ 0);
+ struct SYNC_IBF *ibf_b = SYNC_ibf_create (SYNC_IBF_MIN_BUCKETS,
+ SYNC_IBF_HASH_NUM,
+ 0);
+ struct SYNC_IBFKey key;
+
+ FAILIF ( (NULL == ibf_a) ||
+ (NULL == ibf_b) );
+ for (unsigned int i = 0; i < 30; i++)
+ {
+ key_of (i,
+ &key);
+ if ( (i < 10) ||
+ (i >= 20) )
+ SYNC_ibf_insert (ibf_a,
+ &key);
+ if ( (i >= 10) )
+ SYNC_ibf_insert (ibf_b,
+ &key);
+ }
+
+ SYNC_ibf_subtract (ibf_a,
+ ibf_b);
+ {
+ bool have[30] = { false };
+ int16_t side[30] = { 0 };
+
+ for (;;)
+ {
+ enum GNUNET_GenericReturnValue res;
+ int16_t got_side;
+ struct SYNC_IBFKey got_key;
+
+ res = SYNC_ibf_decode (ibf_a,
+ &got_side,
+ &got_key);
+ if (GNUNET_YES != res)
+ {
+ FAILIF (GNUNET_NO != res);
+ break;
+ }
+ {
+ const unsigned int i = (unsigned int) got_key.nonce[0];
+
+ FAILIF (i >= 30);
+ FAILIF ((got_side != 1) && (got_side != -1));
+ FAILIF (have[i]);
+ have[i] = true;
+ side[i] = got_side;
+ }
+ }
+ for (unsigned int i = 0; i < 30; i++)
+ {
+ if (i < 10)
+ FAILIF (! have[i] || (1 != side[i]));
+ else if (i < 20)
+ FAILIF (! have[i] || (-1 != side[i]));
+ else
+ FAILIF (have[i]);
+ }
+ }
+ SYNC_ibf_destroy (ibf_b);
+ SYNC_ibf_destroy (ibf_a);
+ return 0;
+}
+
+
+/**
+ * The serialized form round-trips, and mismatching parameters are
+ * rejected.
+ *
+ * @return 0 on success
+ */
+static int
+test_serialize (void)
+{
+ struct SYNC_IBF *ibf;
+ struct SYNC_IBF *ibf2;
+ struct SYNC_IBFKey key;
+ struct SYNC_IBFKey got_key;
+ size_t size;
+ void *data;
+
+ ibf = SYNC_ibf_create (SYNC_IBF_MIN_BUCKETS,
+ SYNC_IBF_HASH_NUM,
+ 42);
+ FAILIF (NULL == ibf);
+ for (unsigned int i = 0; i < 20; i++)
+ {
+ key_of (i,
+ &key);
+ SYNC_ibf_insert (ibf,
+ &key);
+ }
+ size = SYNC_ibf_get_serialized_size (ibf);
+ FAILIF (size != ((size_t) SYNC_IBF_MIN_BUCKETS) * SYNC_IBF_BUCKET_SIZE);
+ data = GNUNET_malloc (size);
+ SYNC_ibf_serialize (ibf,
+ data);
+ ibf2 = SYNC_ibf_deserialize (data,
+ SYNC_IBF_MIN_BUCKETS,
+ SYNC_IBF_HASH_NUM,
+ 42);
+ FAILIF (NULL == ibf2);
+ FAILIF (NULL !=
+ SYNC_ibf_deserialize (data,
+ 0,
+ SYNC_IBF_HASH_NUM,
+ 42));
+ {
+ int16_t side;
+ unsigned int got = 0;
+
+ for (;;)
+ {
+ enum GNUNET_GenericReturnValue res;
+
+ res = SYNC_ibf_decode (ibf2,
+ &side,
+ &got_key);
+ if (GNUNET_YES != res)
+ {
+ FAILIF (GNUNET_NO != res);
+ break;
+ }
+ got++;
+ }
+ FAILIF (got != 20);
+ }
+ SYNC_ibf_destroy (ibf2);
+ GNUNET_free (data);
+ SYNC_ibf_destroy (ibf);
+ return 0;
+}
+
+
+/**
+ * Bucket counts are powers of two within the bounds.
+ *
+ * @return 0 on success
+ */
+static int
+test_compute_bucket_count (void)
+{
+ FAILIF (SYNC_ibf_compute_bucket_count (0) != SYNC_IBF_MIN_BUCKETS);
+ FAILIF (SYNC_ibf_compute_bucket_count (1) != SYNC_IBF_MIN_BUCKETS);
+ FAILIF (SYNC_ibf_compute_bucket_count (1000) != 1024);
+ FAILIF (SYNC_ibf_compute_bucket_count (100000) != SYNC_IBF_MAX_BUCKETS);
+ return 0;
+}
+
+
+int
+main (int argc,
+ char **argv)
+{
+ (void) argc;
+ (void) argv;
+ FAILIF (0 != test_insert_remove ());
+ FAILIF (0 != test_decode_difference ());
+ FAILIF (0 != test_serialize ());
+ FAILIF (0 != test_compute_bucket_count ());
+ return 0;
+}
+
+
+/* end of test_sync_ibf.c */
+\ No newline at end of file
