diff options
author | Christian Grothoff <christian@grothoff.org> | 2021-01-19 15:55:28 +0100 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2021-01-19 15:55:28 +0100 |
commit | 6568e36a7cd34d29dddf92ddb31ede75dcfe06e6 (patch) | |
tree | 0fe72f71a1d26d8f467479c8c4b810a5fb695cbb | |
parent | e52742fa7251cfa6e333b07b11683e059ae2b63e (diff) | |
download | lsd0003-6568e36a7cd34d29dddf92ddb31ede75dcfe06e6.tar.gz lsd0003-6568e36a7cd34d29dddf92ddb31ede75dcfe06e6.zip |
answers inline
-rw-r--r-- | draft-summermatter-set-union.xml | 43 |
1 files changed, 39 insertions, 4 deletions
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml index e32f905..ab668d8 100644 --- a/draft-summermatter-set-union.xml +++ b/draft-summermatter-set-union.xml | |||
@@ -1068,14 +1068,16 @@ hashSum | 0x0101 | 0x0101 | 0x5050 | 0000 | | |||
1068 | <dd> | 1068 | <dd> |
1069 | the type of SETU_P2P_OPERATION_REQUEST as registered in <xref target="gana" format="title" />, in network byte order. | 1069 | the type of SETU_P2P_OPERATION_REQUEST as registered in <xref target="gana" format="title" />, in network byte order. |
1070 | </dd> | 1070 | </dd> |
1071 | <dt>OPERATION TYPE</dt> | 1071 | <!-- dt>OPERATION TYPE</dt> |
1072 | <dd> | 1072 | <dd> |
1073 | is a 32-bit unsigned integer which describes the type of operation that should be initiated on the set. The filed can have three | 1073 | is a 32-bit unsigned integer which describes the type of operation that should be initiated on the set. The filed can have three |
1074 | different value NONE, INTERSECTION and UNION, numeric represented by 0,1 and 2. <!-- @Christian can you check? --> | 1074 | different value NONE, INTERSECTION and UNION, numeric represented by 0,1 and 2. <!-- @Christian can you check?: Right, alas we |
1075 | here only do UNION and INTERSECTION is a completely different protocol => we shall simply REMOVE this field. Hence commented out here: | ||
1076 | reminder to _remove_ in implementation! | ||
1075 | NONE should never occur and signals the set supports no operation and is just for local use. | 1077 | NONE should never occur and signals the set supports no operation and is just for local use. |
1076 | INTERSECTION returns only elements that are in both sets and the default case UNION, return all | 1078 | INTERSECTION returns only elements that are in both sets and the default case UNION, return all |
1077 | elements that are in at least one of the sets. | 1079 | elements that are in at least one of the sets. |
1078 | </dd> | 1080 | </dd --> |
1079 | <dt>ELEMENT COUNT</dt> | 1081 | <dt>ELEMENT COUNT</dt> |
1080 | <dd> | 1082 | <dd> |
1081 | is the number of the elements the requesting party has in its set, as a 32-bit unsigned integer in network byte order. | 1083 | 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 | | |||
1162 | The IDSUMS The HASHSUMS is calculated as a standard CRC32 check sum from | 1164 | The IDSUMS The HASHSUMS is calculated as a standard CRC32 check sum from |
1163 | the key of the element. | 1165 | the key of the element. |
1164 | <!-- @Christian: I dont have a clue how this is done... The code is very hard to read can you explain the | 1166 | <!-- @Christian: I dont have a clue how this is done... The code is very hard to read can you explain the |
1165 | salt_key function in gnunet-service-set_union.c file and the ibf_insert_into (why exponentiation? ^=) in the ibf.c | 1167 | salt_key function in gnunet-service-set_union.c file |
1168 | |||
1169 | CG: Eh, you should really read in setu/, not in set/. Alas, this function is the same. | ||
1170 | |||
1171 | The goal of salt_key is to modify a given IBF key based on the salt (so we | ||
1172 | end up with different material depending on the salt). We only use the | ||
1173 | lowest 6 bits of the salt (hopefully enough!): | ||
1174 | |||
1175 | int s = salt % 64; | ||
1176 | uint64_t x = k_in->key_val; // that's the real input: at 64 bit value | ||
1177 | |||
1178 | /* rotate ibf key */ | ||
1179 | x = (x >> s) | (x << (64 - s)); // We simply to a bit rotation by 's' | ||
1180 | k_out->key_val = x; // That's the final output. | ||
1181 | |||
1182 | In some languages, this would simply be: | ||
1183 | result = (input <<< salt); // bit rotation operator | ||
1184 | |||
1185 | @Christian and the ibf_insert_into (why exponentiation? ^=) in the ibf.c | ||
1186 | |||
1187 | CG: ^= is XOR in C (A ^=B; is basically "A := A XOR B"), _not_ exponentiation! | ||
1188 | |||
1166 | The only thing i found out was that the Hashsum in the current implementation is calculated with CRC32. | 1189 | The only thing i found out was that the Hashsum in the current implementation is calculated with CRC32. |
1190 | |||
1191 | Not just. We take the 64-bit ID value. First, using 'CRC32' to compute | ||
1192 | a 32-byte value. Take that modulo % buckets to get a bucket index. | ||
1193 | Then shift the 32 bits high, or with 'i' (loop!) to set 32 low bits, | ||
1194 | and again CRC32 to compute the next bucket. *IF* this formula returns | ||
1195 | the same bucket twice, skip (so we guarantee hash_num disjoint buckets). | ||
1196 | Note that the code had a bug, pushing a fix now: | ||
1197 | |||
1198 | if (dst[j] == bucket) | ||
1199 | must be | ||
1200 | if (dst[j] == bucket % ibf->size) | ||
1201 | |||
1167 | --> | 1202 | --> |
1168 | </t> | 1203 | </t> |
1169 | 1204 | ||