commit 7e26639340f951684c7593b400d8f4fb68a3977c
parent fa2765cf3c007c38725a1093c4502e05b63002f9
Author: Elias Summermatter <elias.summermatter@seccom.ch>
Date: Sun, 13 Jun 2021 20:52:52 +0200
Added some se message description
Diffstat:
1 file changed, 100 insertions(+), 58 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -1472,8 +1472,16 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
- | MSG SIZE | MSG TYPE | HASHES
- +-----+-----+-----+-----+
+ | MSG SIZE | MSG TYPE | HASH 1
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ ... ...
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | HASH 1 | HASH 2
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ ... ...
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | HASH 2 | HASH n
+ +-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
]]></artwork>
@@ -1573,6 +1581,14 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
+-----+-----+-----+-----+-----+-----+-----+-----+
| MSG SIZE | MSG TYPE | HASH
+-----+-----+-----+-----+
+ ... ...
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | HASH 1 | HASH 2
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ ... ...
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | HASH 2 | HASH n
+ +-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
]]></artwork>
@@ -1589,10 +1605,9 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
</dd>
<dt>HASH</dt>
<dd>
- is a 512-bit Hash of the element that is demanded.
+ contains one or more successive SHA 512-bit hashes of the elements that is demanded.
</dd>
</dl>
- <!-- FIXME: DEMAND was defined as a variable-size message that CAN include multiple HASH values in one message. Current code does not use this, but we should continue to define it as such in the protocol! -->
</section>
</section>
@@ -1850,14 +1865,41 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<dd>
is a 64-bit unsigned integer that is defined by the size of the set the SE is
</dd>
+ <!-- CORRECT -->
<dt>SE-SLICES</dt>
<dd>
- is variable in size and contains the same structure as the IBF-SLICES field in the <xref target="messages_ibf" format="title" /> message.
+ <t>
+ are variable numbers of slices in an array. A single slice can contain one or more Strata Estimators which
+ contain multiple IBFs as described in IBF-SLICES in <xref target="messages_ibf_structure" format="default"/>.
+ A SE slice can contain one to eight Strata Estimators which contain 32 (Defined as Constant SE_STRATA_COUNT) IBFs. Every IBF in
+ a SE contains 79 Buckets.
+ </t>
+ <t>
+ The different SEs are build as in detail described as in section <xref target="performance_multi_se" format="default"/>.
+ Simply put, the IBFs in each SE are serialized as described in <xref target="messages_ibf_structure" format="default"/> starting with the highest stratum.
+ Then the created SEs are appended one after the other starting with the SE that was created with a salt of zero.
+
+ </t>
</dd>
- <!-- FIXME: this is very imprecise, as there are multiple IBFs with that have
- been sampled, and then again multiple IBFs with a different IBF-salt.
- Please be MUCH more precise here! -->
</dl>
+ <figure anchor="figure_se_slice">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ SE-SLICE
+ 0 8 16 24 32 40 48 56
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | SE 1 [IBF 1] |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ ... ...
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | SE 1 [IBF 30] |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | SE 2 [IBF 1] |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ ... ...
+ / /
+ / /
+ ]]></artwork>
+ </figure>
</section>
</section>
@@ -1988,46 +2030,46 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
# IBF_MIN_SIZE = 37: The minimal size of an IBF
# MAX_BUCKETS_PER_MESSAGE: Custom value depending on the underlying protocol
# INPUTS:
-# avg_element_size: The average element size
-# local_set_size: The initial local set size
-# remote_set_size: The remote set size
-# est_local_set_diff: the estimated local set difference calculated by the SE
-# est_remote_set_diff: the estimated remote set difference calculated by the SE
-# rtt_tradeoff: the tradeoff between round trips and bandwidth
+# avg_es: The average element size
+# lss: The initial local set size
+# rss: The remote set size
+# lsd: the estimated local set difference calculated by the SE
+# rsd: the estimated remote set difference calculated by the SE
+# rtt: the tradeoff between round trips and bandwidth
# OUTPUT:
# FULL_SYNC_REMOTE_SENDING_FIRST, FULL_SYNC_LOCAL_SENDING_FIRST or DIFFERENTIAL_SYNC
-FUNCTION decide_operation_mode(avg_element_size,
- local_set_size,
- remote_set_size,
- est_local_set_diff
- est_remote_set_diff,
- rtt_tradeoff)
+FUNCTION decide_operation_mode(avg_es,
+ lss,
+ rss,
+ lsd
+ rsd,
+ rtt)
# If a set size is zero always do full sync
- IF (0 == remote_set_size)
+ IF (0 == rss)
RETURN FULL_SYNC_LOCAL_SENDING_FIRST
IF END
- IF (0 == local_set_size)
+ IF (0 == lss)
RETURN FULL_SYNC_REMOTE_SENDING_FIRST
IF END
# Estimate required transferred bytes when doing a full synchronisation
# and transmitting local set first.
- estimated_total_diff = est_set_diff_remote + est_local_set_diff
- total_elements_local_send = est_remote_set_diff + local_set_size
- total_bytes_local_send = (avg_element_size * total_elements_local_send)
+ estimated_total_diff = est_set_diff_remote + lsd
+ total_elements_local_send = rsd + lss
+ total_bytes_local_send = (avg_es * total_elements_local_send)
+ (total_elements_local_send * sizeof(ELEMENT_MSG_HEADER))
+ (sizeof(FULL_DONE_MSG_HEADER) * 2)
- + RTT_MIN_FULL * rtt_tradeoff
+ + RTT_MIN_FULL * rtt
# Estimate required transferred bytes when doing a full synchronisation
# and transmitting remote set first.
- total_elements_remote_send = est_local_set_diff + remote_set_size
- total_bytes_remote_send = (avg_element_size * total_elements_remote_send)
+ total_elements_remote_send = lsd + rss
+ total_bytes_remote_send = (avg_es * total_elements_remote_send)
+ ( total_elements_remote_send * sizeof(ELEMENT_MSG_HEADER))
+ (sizeof(FULL_DONE_MSG_HEADER) * 2)
- + (RTT_MIN_FULL + 0.5) * rtt_tradeoff
+ + (RTT_MIN_FULL + 0.5) * rtt
+ sizeof(REQUEST_FULL_MSG)
# Estimate required transferred bytes when doing a differential synchronisation
@@ -2041,8 +2083,8 @@ FUNCTION decide_operation_mode(avg_element_size,
# Estimate average counter length with variable counter
estimated_counter_size = MIN (
- 2 * LOG2(local_set_size / ibf_bucket_count),
- LOG2(local_set_size)
+ 2 * LOG2(lss / ibf_bucket_count),
+ LOG2(lss)
)
counter_bytes = estimated_counter_size / 8
@@ -2053,7 +2095,7 @@ FUNCTION decide_operation_mode(avg_element_size,
+ ibf_bucket_count * counter_bytes * 1.2
done_size = sizeof(DONE_HEADER)
- element_size = (avg_element_size + sizeof(ELEMENT_MSG_HEADER))
+ element_size = (avg_es + sizeof(ELEMENT_MSG_HEADER))
* estimated_total_diff
inquery_size = (sizeof(IBF_KEY) + sizeof(INQUERY_MSG_HEADER))
* estimated_total_diff
@@ -2064,7 +2106,7 @@ FUNCTION decide_operation_mode(avg_element_size,
total_bytes_diff = (element_size + done_size + inquery_size
+ demand_size + offer_size + ibf_bytes)
- + DIFFERENTIAL_RTT_MEAN * rtt_tradeoff
+ + DIFFERENTIAL_RTT_MEAN * rtt
# Decide for a optimal mode of operation
@@ -2103,24 +2145,24 @@ FUNCTION decide_operation_mode(avg_element_size,
# CONSTANTS:
# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if decoding fails
# Inputs:
-# set_difference: Estimated set difference
+# sd: Estimated set difference
# Output:
# next_size: Size of the initial IBF
-FUNCTION initial_ibf_size(set_difference)
- return MAX(37, IBF_BUCKET_NUMBER_FACTOR * set_difference);
+FUNCTION initial_ibf_size(sd)
+ return MAX(37, IBF_BUCKET_NUMBER_FACTOR * sd);
FUNCTION END
# CONSTANTS:
# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if decoding fails
# Inputs:
-# decoded_elements: Number of elements that have been successfully decoded
-# last_ibf_size: The number of buckets of the last IBF
+# de: Number of elements that have been successfully decoded
+# lis: The number of buckets of the last IBF
# Output:
# number of buckets for the next IBF
-FUNCTION get_next_ibf_size(decoded_elements, last_ibf_size)
- next_size = IBF_BUCKET_NUMBER_FACTOR * (last_ibf_size - decoded_elements)
+FUNCTION get_next_ibf_size(de, lis)
+ next_size = IBF_BUCKET_NUMBER_FACTOR * (lis - de)
return MAX(37, next_size);
FUNCTION END
]]></artwork>
@@ -2234,23 +2276,23 @@ FUNCTION pack_counter(ibf, offset, count)
# offset: The offset which defines the starting point from which bucket
the packed operation starts
# count: The number of buckets in the array that will be packed
-# counter_bit_length: The bit length of the counter can be found in the
+# cbl: The bit length of the counter can be found in the
ibf message in the ibf_counter_bit_length field
-# packed_data: A byte array which contains the data packed with the pack_counter
+# pd: A byte array which contains the data packed with the pack_counter
function
# OUTPUTS:
# returns: Nothing because the unpacked counter is saved directly into the IBF
-FUNCTION unpack_counter(ibf, offset, count, counter_bit_length, packed_data)
+FUNCTION unpack_counter(ibf, offset, count, cbl, pd)
store = 0
store_bits = 0
byte_ctr = 0
ibf_bucket_ctr = 0
- number_bytes_read = CEILING((count * counter_bit_length) / 8)
+ number_bytes_read = CEILING((count * cbl) / 8)
WHILE ibf_bucket_ctr <= (count -1)
- byte_to_read = packed_data[byte_ctr]
+ byte_to_read = pd[byte_ctr]
byte_ctr++
bit_to_pack_left = 8
@@ -2260,8 +2302,8 @@ FUNCTION unpack_counter(ibf, offset, count, counter_bit_length, packed_data)
IF ibf_bucket_ctr > (count -1)
return
- IF ( store_bits + bit_to_pack_left ) >= counter_bit_length
- bit_use = counter_bit_length - store_bits
+ IF ( store_bits + bit_to_pack_left ) >= cbl
+ bit_use = cbl - store_bits
IF store_bits > 0
store = store << bit_use
@@ -2440,14 +2482,14 @@ FUNCTION END
<figure anchor="security_generic_functions_check_valid_state_code">
<artwork name="" type="" align="left" alt=""><