sync_ibf.c (13340B)
1 /* 2 This file is part of TALER 3 Copyright (C) 2026 Taler Systems SA 4 5 TALER is free software; you can redistribute it and/or modify it under the 6 terms of the GNU Affero General Public License as published by the Free Software 7 Foundation; either version 3, or (at your option) any later version. 8 9 TALER is distributed in the hope that it will be useful, but WITHOUT ANY 10 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR 11 A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details. 12 13 You should have received a copy of the GNU Affero General Public License along with 14 TALER; see the file COPYING. If not, see <http://www.gnu.org/licenses/> 15 */ 16 /** 17 * @file util/sync_ibf.c 18 * @brief invertible bloom filter for backup reconciliation (DD 92) 19 * @author Iván Ávalos 20 */ 21 22 /** 23 * The filter is a set of @a size buckets, each holding: 24 * 25 * +--------------------------+ 26 * | Counter (2 byte) | 27 * +--------------------------+ 28 * | Key sum (88 byte) | XOR of the elements' keys 29 * +--------------------------+ 30 * | Key hash sum (8 byte) | XOR of the elements' key hashes 31 * +--------------------------+ 32 * 33 * Testing membership is not possible (unlike a plain bloom filter), 34 * but the filter is invertible: subtracting the filters of two sets 35 * yields the filter of their symmetric difference, and peeling pure 36 * buckets decodes the differing elements one by one. This is what 37 * makes targeted pulls possible: given the server's filter and its 38 * own, a wallet can enumerate exactly the blocks that were added, 39 * rewritten or deleted since it last looked. 40 * 41 * Bucket indices derive from successive 32-bit words of the SHA-512 42 * over element + mixing prefix, re-hashing when the words run out 43 * (as in GNUnet's bloom filters); duplicate indices are skipped, as 44 * in GNUnet's invertible-bloom-filter implementation (ibf.c in the 45 * SET service). 46 */ 47 #include "platform.h" 48 #include <gnunet/gnunet_util_lib.h> 49 #include "sync/sync_ibf.h" 50 51 52 /** 53 * The filter. 54 */ 55 struct SYNC_IBF 56 { 57 /** 58 * Number of buckets. 59 */ 60 uint32_t size; 61 62 /** 63 * Number of hash functions per element. 64 */ 65 unsigned int hash_num; 66 67 /** 68 * Mixing salt hashed with every element. 69 */ 70 uint32_t prefix; 71 72 /** 73 * Per-bucket counters (number of insertions). 74 */ 75 int16_t *count; 76 77 /** 78 * Per-bucket XOR sums of the element keys. 79 */ 80 unsigned char *key_sum; 81 82 /** 83 * Per-bucket XOR sums of the element key hashes. 84 */ 85 unsigned char *key_hash_sum; 86 }; 87 88 89 /** 90 * Stream of 32-bit words over a hash chain: the words of the mingled 91 * hash, followed by the words of its hash, and so on, enough for any 92 * number of distinct bucket indices. 93 */ 94 struct WordStream 95 { 96 /** 97 * Current hash of the chain. 98 */ 99 unsigned char hash[64]; 100 101 /** 102 * Next word to read from @e hash. 103 */ 104 unsigned int slot; 105 }; 106 107 108 /** 109 * Start the word stream over SHA-512(element || prefix). 110 * 111 * @param ws stream to initialize 112 * @param key element to hash 113 * @param prefix mixing salt (network byte order value) 114 */ 115 static void 116 ws_init (struct WordStream *ws, 117 const struct SYNC_IBFKey *key, 118 uint32_t prefix) 119 { 120 unsigned char input[SYNC_IBF_KEY_SIZE + 4]; 121 uint32_t p = htonl (prefix); 122 123 memcpy (input, 124 key, 125 SYNC_IBF_KEY_SIZE); 126 memcpy (input + SYNC_IBF_KEY_SIZE, 127 &p, 128 sizeof (p)); 129 GNUNET_CRYPTO_hash (input, 130 sizeof (input), 131 (struct GNUNET_HashCode *) ws->hash); 132 ws->slot = 0; 133 } 134 135 136 /** 137 * Read the next word of the stream. 138 * 139 * @param ws stream to read from 140 * @return next 32-bit word, in host byte order 141 */ 142 static uint32_t 143 ws_next (struct WordStream *ws) 144 { 145 uint32_t w; 146 147 if (ws->slot >= (sizeof (ws->hash) / sizeof (uint32_t))) 148 { 149 GNUNET_CRYPTO_hash (ws->hash, 150 sizeof (ws->hash), 151 (struct GNUNET_HashCode *) ws->hash); 152 ws->slot = 0; 153 } 154 memcpy (&w, 155 ws->hash + ws->slot * sizeof (w), 156 sizeof (w)); 157 ws->slot++; 158 return ntohl (w); 159 } 160 161 162 /** 163 * Store the bucket indices of an element in @a dst, one per hash 164 * function, skipping duplicates. 165 * 166 * @param ibf filter the element maps into (for size and hash_num) 167 * @param key element 168 * @param dst array of @a hash_num bucket indices 169 */ 170 static void 171 ibf_get_indices (const struct SYNC_IBF *ibf, 172 const struct SYNC_IBFKey *key, 173 int *dst) 174 { 175 struct WordStream ws; 176 uint32_t filled = 0; 177 178 ws_init (&ws, 179 key, 180 ibf->prefix); 181 while (filled < ibf->hash_num) 182 { 183 uint32_t bucket = ws_next (&ws) % ibf->size; 184 bool dup = false; 185 186 for (uint32_t j = 0; j < filled; j++) 187 { 188 if (dst[j] == (int) bucket) 189 { 190 dup = true; 191 break; 192 } 193 } 194 if (! dup) 195 dst[filled++] = bucket; 196 } 197 } 198 199 200 /** 201 * Compute the key hash of an element: the first 8 bytes of SHA-512 202 * over the key. 203 * 204 * @param key element 205 * @param[out] kh where to store the key hash 206 */ 207 static void 208 ibf_key_hash (const struct SYNC_IBFKey *key, 209 unsigned char kh[SYNC_IBF_KEY_HASH_SIZE]) 210 { 211 struct GNUNET_HashCode h; 212 213 GNUNET_CRYPTO_hash (key, 214 SYNC_IBF_KEY_SIZE, 215 &h); 216 memcpy (kh, 217 &h, 218 SYNC_IBF_KEY_HASH_SIZE); 219 } 220 221 222 /** 223 * XOR @a size bytes of @a src into @a dst. 224 */ 225 static void 226 xor_into (unsigned char *dst, 227 const unsigned char *src, 228 size_t size) 229 { 230 for (size_t i = 0; i < size; i++) 231 dst[i] ^= src[i]; 232 } 233 234 235 /** 236 * Insert an element with sign @a side (+1 insert, -1 remove): the 237 * counterpart of inserting it on the opposite side peels it out. 238 * 239 * @param ibf filter to manipulate 240 * @param key element 241 * @param buckets its bucket indices 242 * @param side +1 or -1 243 */ 244 static void 245 ibf_insert_into (struct SYNC_IBF *ibf, 246 const struct SYNC_IBFKey *key, 247 const int *buckets, 248 int16_t side) 249 { 250 unsigned char kh[SYNC_IBF_KEY_HASH_SIZE]; 251 252 ibf_key_hash (key, 253 kh); 254 for (unsigned int i = 0; i < ibf->hash_num; i++) 255 { 256 const int bucket = buckets[i]; 257 258 ibf->count[bucket] += side; 259 xor_into (ibf->key_sum + ((size_t) bucket) * SYNC_IBF_KEY_SIZE, 260 (const unsigned char *) key, 261 SYNC_IBF_KEY_SIZE); 262 xor_into (ibf->key_hash_sum + ((size_t) bucket) * SYNC_IBF_KEY_HASH_SIZE, 263 kh, 264 SYNC_IBF_KEY_HASH_SIZE); 265 } 266 } 267 268 269 uint32_t 270 SYNC_ibf_compute_bucket_count (uint32_t block_count) 271 { 272 uint32_t size = SYNC_IBF_MIN_BUCKETS; 273 274 if (block_count > SYNC_IBF_MAX_BUCKETS) 275 return SYNC_IBF_MAX_BUCKETS; 276 while ( (size < SYNC_IBF_MAX_BUCKETS) && 277 (size < block_count) ) 278 size *= 2; 279 return size; 280 } 281 282 283 struct SYNC_IBF * 284 SYNC_ibf_create (uint32_t bucket_count, 285 unsigned int hash_num, 286 uint32_t prefix) 287 { 288 struct SYNC_IBF *ibf; 289 290 if ( (0 == bucket_count) || 291 (0 == hash_num) ) 292 return NULL; 293 ibf = GNUNET_new (struct SYNC_IBF); 294 ibf->size = bucket_count; 295 ibf->hash_num = hash_num; 296 ibf->prefix = prefix; 297 ibf->count = GNUNET_malloc (bucket_count * sizeof (int16_t)); 298 ibf->key_sum = GNUNET_malloc ((size_t) bucket_count * SYNC_IBF_KEY_SIZE); 299 ibf->key_hash_sum = GNUNET_malloc ((size_t) bucket_count 300 * SYNC_IBF_KEY_HASH_SIZE); 301 return ibf; 302 } 303 304 305 struct SYNC_IBF * 306 SYNC_ibf_deserialize (const void *data, 307 uint32_t bucket_count, 308 unsigned int hash_num, 309 uint32_t prefix) 310 { 311 struct SYNC_IBF *ibf; 312 313 if ( (NULL == data) || 314 (0 == bucket_count) || 315 (0 == hash_num) ) 316 return NULL; 317 ibf = SYNC_ibf_create (bucket_count, 318 hash_num, 319 prefix); 320 if (NULL == ibf) 321 return NULL; 322 for (uint32_t i = 0; i < bucket_count; i++) 323 { 324 const unsigned char *b = ((const unsigned char *) data) 325 + ((size_t) i) * SYNC_IBF_BUCKET_SIZE; 326 327 memcpy (&ibf->count[i], 328 b, 329 sizeof (int16_t)); 330 ibf->count[i] = ntohs (ibf->count[i]); 331 memcpy (ibf->key_sum + ((size_t) i) * SYNC_IBF_KEY_SIZE, 332 b + 2, 333 SYNC_IBF_KEY_SIZE); 334 memcpy (ibf->key_hash_sum + ((size_t) i) * SYNC_IBF_KEY_HASH_SIZE, 335 b + 2 + SYNC_IBF_KEY_SIZE, 336 SYNC_IBF_KEY_HASH_SIZE); 337 } 338 return ibf; 339 } 340 341 342 size_t 343 SYNC_ibf_get_serialized_size (const struct SYNC_IBF *ibf) 344 { 345 if (NULL == ibf) 346 return 0; 347 return ((size_t) ibf->size) * SYNC_IBF_BUCKET_SIZE; 348 } 349 350 351 void 352 SYNC_ibf_serialize (const struct SYNC_IBF *ibf, 353 void *data) 354 { 355 for (uint32_t i = 0; i < ibf->size; i++) 356 { 357 unsigned char *b = ((unsigned char *) data) 358 + ((size_t) i) * SYNC_IBF_BUCKET_SIZE; 359 int16_t count = htons (ibf->count[i]); 360 361 memcpy (b, 362 &count, 363 sizeof (count)); 364 memcpy (b + 2, 365 ibf->key_sum + ((size_t) i) * SYNC_IBF_KEY_SIZE, 366 SYNC_IBF_KEY_SIZE); 367 memcpy (b + 2 + SYNC_IBF_KEY_SIZE, 368 ibf->key_hash_sum + ((size_t) i) * SYNC_IBF_KEY_HASH_SIZE, 369 SYNC_IBF_KEY_HASH_SIZE); 370 } 371 } 372 373 374 void 375 SYNC_ibf_destroy (struct SYNC_IBF *ibf) 376 { 377 if (NULL == ibf) 378 return; 379 GNUNET_free (ibf->key_hash_sum); 380 GNUNET_free (ibf->key_sum); 381 GNUNET_free (ibf->count); 382 GNUNET_free (ibf); 383 } 384 385 386 void 387 SYNC_ibf_insert (struct SYNC_IBF *ibf, 388 const struct SYNC_IBFKey *key) 389 { 390 int buckets[ibf->hash_num]; 391 392 GNUNET_assert (ibf->hash_num <= ibf->size); 393 ibf_get_indices (ibf, 394 key, 395 buckets); 396 ibf_insert_into (ibf, 397 key, 398 buckets, 399 1); 400 } 401 402 403 void 404 SYNC_ibf_remove (struct SYNC_IBF *ibf, 405 const struct SYNC_IBFKey *key) 406 { 407 int buckets[ibf->hash_num]; 408 409 GNUNET_assert (ibf->hash_num <= ibf->size); 410 ibf_get_indices (ibf, 411 key, 412 buckets); 413 ibf_insert_into (ibf, 414 key, 415 buckets, 416 -1); 417 } 418 419 420 void 421 SYNC_ibf_subtract (struct SYNC_IBF *ibf1, 422 const struct SYNC_IBF *ibf2) 423 { 424 GNUNET_assert (ibf1->size == ibf2->size); 425 GNUNET_assert (ibf1->hash_num == ibf2->hash_num); 426 for (uint32_t i = 0; i < ibf1->size; i++) 427 { 428 ibf1->count[i] -= ibf2->count[i]; 429 xor_into (ibf1->key_sum + ((size_t) i) * SYNC_IBF_KEY_SIZE, 430 ibf2->key_sum + ((size_t) i) * SYNC_IBF_KEY_SIZE, 431 SYNC_IBF_KEY_SIZE); 432 xor_into (ibf1->key_hash_sum 433 + ((size_t) i) * SYNC_IBF_KEY_HASH_SIZE, 434 ibf2->key_hash_sum 435 + ((size_t) i) * SYNC_IBF_KEY_HASH_SIZE, 436 SYNC_IBF_KEY_HASH_SIZE); 437 } 438 } 439 440 441 /** 442 * Test if the filter is empty, i.e. all counts and sums are zero. 443 * 444 * @param ibf filter to test 445 * @return #GNUNET_YES if empty 446 */ 447 static int 448 ibf_is_empty (const struct SYNC_IBF *ibf) 449 { 450 for (uint32_t i = 0; i < ibf->size; i++) 451 { 452 if (0 != ibf->count[i]) 453 return GNUNET_NO; 454 for (unsigned int j = 0; j < SYNC_IBF_KEY_HASH_SIZE; j++) 455 if (0 != ibf->key_hash_sum[((size_t) i) * SYNC_IBF_KEY_HASH_SIZE + j]) 456 return GNUNET_NO; 457 for (unsigned int j = 0; j < SYNC_IBF_KEY_SIZE; j++) 458 if (0 != ibf->key_sum[((size_t) i) * SYNC_IBF_KEY_SIZE + j]) 459 return GNUNET_NO; 460 } 461 return GNUNET_YES; 462 } 463 464 465 enum GNUNET_GenericReturnValue 466 SYNC_ibf_decode (struct SYNC_IBF *ibf, 467 int16_t *ret_side, 468 struct SYNC_IBFKey *ret_key) 469 { 470 for (uint32_t i = 0; i < ibf->size; i++) 471 { 472 struct SYNC_IBFKey peeled; 473 unsigned char kh[SYNC_IBF_KEY_HASH_SIZE]; 474 int buckets[ibf->hash_num]; 475 476 /* only pure buckets can be decoded */ 477 if ( (1 != ibf->count[i]) && 478 (-1 != ibf->count[i]) ) 479 continue; 480 481 /* the key sum of a pure bucket is the key: work on a copy, since 482 peeling XORs it back out of the bucket this key came from */ 483 memcpy (&peeled, 484 ibf->key_sum + ((size_t) i) * SYNC_IBF_KEY_SIZE, 485 SYNC_IBF_KEY_SIZE); 486 487 /* check the key's hash against the bucket's hash sum */ 488 ibf_key_hash (&peeled, 489 kh); 490 { 491 bool kh_ok = true; 492 493 for (unsigned int j = 0; j < SYNC_IBF_KEY_HASH_SIZE; j++) 494 if (kh[j] != 495 ibf->key_hash_sum[((size_t) i) * SYNC_IBF_KEY_HASH_SIZE + j]) 496 { 497 kh_ok = false; 498 break; 499 } 500 if (! kh_ok) 501 continue; 502 } 503 504 /* the key must map to this bucket itself */ 505 ibf_get_indices (ibf, 506 &peeled, 507 buckets); 508 { 509 bool hit = false; 510 511 for (unsigned int j = 0; j < ibf->hash_num; j++) 512 { 513 if (buckets[j] == (int) i) 514 { 515 hit = true; 516 break; 517 } 518 } 519 if (! hit) 520 continue; 521 } 522 523 if (NULL != ret_side) 524 *ret_side = ibf->count[i]; 525 if (NULL != ret_key) 526 *ret_key = peeled; 527 528 /* insert on the opposite side, peeling the element out */ 529 ibf_insert_into (ibf, 530 &peeled, 531 buckets, 532 -ibf->count[i]); 533 534 return GNUNET_YES; 535 } 536 537 if (GNUNET_YES == ibf_is_empty (ibf)) 538 return GNUNET_NO; 539 return GNUNET_SYSERR; 540 } 541 542 543 /* end of sync_ibf.c */