commit 6568e36a7cd34d29dddf92ddb31ede75dcfe06e6
parent e52742fa7251cfa6e333b07b11683e059ae2b63e
Author: Christian Grothoff <christian@grothoff.org>
Date: Tue, 19 Jan 2021 15:55:28 +0100
answers inline
Diffstat:
1 file changed, 39 insertions(+), 4 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -1068,14 +1068,16 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 |
<dd>
the type of SETU_P2P_OPERATION_REQUEST as registered in <xref target="gana" format="title" />, in network byte order.
</dd>
- <dt>OPERATION TYPE</dt>
+ <!-- dt>OPERATION TYPE</dt>
<dd>
is a 32-bit unsigned integer which describes the type of operation that should be initiated on the set. The filed can have three
- different value NONE, INTERSECTION and UNION, numeric represented by 0,1 and 2. <!-- @Christian can you check? -->
+ different value NONE, INTERSECTION and UNION, numeric represented by 0,1 and 2. <!-- @Christian can you check?: Right, alas we
+ here only do UNION and INTERSECTION is a completely different protocol => we shall simply REMOVE this field. Hence commented out here:
+ reminder to _remove_ in implementation!
NONE should never occur and signals the set supports no operation and is just for local use.
INTERSECTION returns only elements that are in both sets and the default case UNION, return all
elements that are in at least one of the sets.
- </dd>
+ </dd -->
<dt>ELEMENT COUNT</dt>
<dd>
is the number of the elements the requesting party has in its set, as a 32-bit unsigned integer in network byte order.
@@ -1162,8 +1164,41 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 |
The IDSUMS The HASHSUMS is calculated as a standard CRC32 check sum from
the key of the element.
<!-- @Christian: I dont have a clue how this is done... The code is very hard to read can you explain the
- salt_key function in gnunet-service-set_union.c file and the ibf_insert_into (why exponentiation? ^=) in the ibf.c
+ salt_key function in gnunet-service-set_union.c file
+
+ CG: Eh, you should really read in setu/, not in set/. Alas, this function is the same.
+
+ The goal of salt_key is to modify a given IBF key based on the salt (so we
+ end up with different material depending on the salt). We only use the
+ lowest 6 bits of the salt (hopefully enough!):
+
+ int s = salt % 64;
+ uint64_t x = k_in->key_val; // that's the real input: at 64 bit value
+
+ /* rotate ibf key */
+ x = (x >> s) | (x << (64 - s)); // We simply to a bit rotation by 's'
+ k_out->key_val = x; // That's the final output.
+
+ In some languages, this would simply be:
+ result = (input <<< salt); // bit rotation operator
+
+ @Christian and the ibf_insert_into (why exponentiation? ^=) in the ibf.c
+
+ CG: ^= is XOR in C (A ^=B; is basically "A := A XOR B"), _not_ exponentiation!
+
The only thing i found out was that the Hashsum in the current implementation is calculated with CRC32.
+
+ Not just. We take the 64-bit ID value. First, using 'CRC32' to compute
+ a 32-byte value. Take that modulo % buckets to get a bucket index.
+ Then shift the 32 bits high, or with 'i' (loop!) to set 32 low bits,
+ and again CRC32 to compute the next bucket. *IF* this formula returns
+ the same bucket twice, skip (so we guarantee hash_num disjoint buckets).
+ Note that the code had a bug, pushing a fix now:
+
+ if (dst[j] == bucket)
+ must be
+ if (dst[j] == bucket % ibf->size)
+
-->
</t>
