commit aa3d59625b1cf688c268c56caaee65494996cd35
parent e3331b5f6fff65df491e138dc06ff1b09eeb6ee6
Author: Elias Summermatter <elias.summermatter@seccom.ch>
Date: Wed, 16 Jun 2021 19:23:51 +0200
Fixed some formating for publication
Diffstat:
1 file changed, 132 insertions(+), 98 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -1215,7 +1215,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
| MSG SIZE | MSG TYPE | ELEMENT COUNT |
+-----+-----+-----+-----+-----+-----+-----+-----+
| APX
- +-----+-----+-----+-----+-----+-----+-----+-----+ /
+ +-----+-----+-----+-----+-----+-----+-----+-----+
/ APPLICATION DATA /
/ /
]]></artwork>
@@ -1274,7 +1274,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
| OFFSET | SALT | IMCS |
+-----+-----+-----+-----+-----+-----+-----+-----+
| IBF-SLICE
- +-----+-----+-----+-----+-----+-----+-----+-----+ /
+ +-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
]]></artwork>
@@ -1417,7 +1417,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
| MSG SIZE | MSG TYPE | E TYPE | PADDING |
+-----+-----+-----+-----+-----+-----+-----+-----+
| E SIZE | DATA
- +-----+-----+ /
+ +-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
]]></artwork>
@@ -1482,11 +1482,11 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
+-----+-----+-----+-----+-----+-----+-----+-----+
... ...
+-----+-----+-----+-----+-----+-----+-----+-----+
- | HASH 1 | HASH 2
+ HASH 1 | HASH 2
+-----+-----+-----+-----+-----+-----+-----+-----+
... ...
+-----+-----+-----+-----+-----+-----+-----+-----+
- | HASH 2 | HASH n
+ HASH 2 | HASH n
+-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
@@ -1502,9 +1502,9 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<dd>
is SETU_P2P_OFFER as registered in <xref target="gana" format="title" /> in network byte order.
</dd>
- <dt>HASHES</dt>
+ <dt>HASH n</dt>
<dd>
- contains one or more successive SHA 512-bit hashes of the elements that are being requested with <em><xref target="messages_inquiry" format="title" /></em> messages.
+ contains n (one or more) successive SHA 512-bit hashes of the elements that are being requested with <em><xref target="messages_inquiry" format="title" /></em> messages.
</dd>
</dl>
</section>
@@ -1533,13 +1533,13 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
+-----+-----+-----+-----+-----+-----+-----+-----+
| MSG SIZE | MSG TYPE | SALT |
+-----+-----+-----+-----+-----+-----+-----+-----+
- | IBF KEY 1 |
+ | IBF KEY 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
- | IBF KEY 2 |
+ | IBF KEY 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
... ...
+-----+-----+-----+-----+-----+-----+-----+-----+
- | IBF KEY n |
+ | IBF KEY n |
+-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
@@ -1557,7 +1557,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
</dd>
<dt>IBF KEY</dt>
<dd>
- contains one or more successive ibf keys (64-bit unsigned integer) for which the inquiry is sent.
+ contains n (one or more) successive ibf keys (64-bit unsigned integer) for which the inquiry is sent.
</dd>
</dl>
</section>
@@ -1585,15 +1585,15 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
- | MSG SIZE | MSG TYPE | HASH
- +-----+-----+-----+-----+
+ | MSG SIZE | MSG TYPE | HASH 1
+ +-----+-----+-----+-----+-----+-----+-----+-----+
... ...
+-----+-----+-----+-----+-----+-----+-----+-----+
- | HASH 1 | HASH 2
+ HASH 1 | HASH 2
+-----+-----+-----+-----+-----+-----+-----+-----+
... ...
+-----+-----+-----+-----+-----+-----+-----+-----+
- | HASH 2 | HASH n
+ HASH 2 | HASH n
+-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
@@ -1609,9 +1609,9 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<dd>
the type of SETU_P2P_DEMAND as registered in <xref target="gana" format="title" /> in network byte order.
</dd>
- <dt>HASH</dt>
+ <dt>HASH n</dt>
<dd>
- contains one or more successive SHA 512-bit hashes of the elements that are being demanded.
+ contains n (one or more) successive SHA 512-bit hashes of the elements that are being demanded.
</dd>
</dl>
</section>
@@ -1636,8 +1636,10 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
- | MSG SIZE | MSG TYPE |
+ | MSG SIZE | MSG TYPE | FINAL CHECKSUM
+-----+-----+-----+-----+-----+-----+-----+-----+
+ / /
+ / /
]]></artwork>
</figure>
@@ -1653,7 +1655,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
</dd>
<dt>FINAL CHECKSUM</dt>
<dd>
- a SHA-512 bit hash of the full set after synchronization. This should ensure that the sets are identical in the end!
+ a SHA-512 hash XOR sum of the full set after synchronization. This should ensure that the sets are identical in the end!
</dd>
</dl>
</section>
@@ -1680,7 +1682,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
| MSG SIZE | MSG TYPE | FINAL CHECKSUM
- +-----+-----+-----+-----+
+ +-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
]]></artwork>
@@ -1697,7 +1699,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
</dd>
<dt> FINAL CHECKSUM</dt>
<dd>
- a SHA-512 bit hash of the full set after synchronization. This should ensure that the sets are identical in the end!
+ a SHA-512 hash XOR sum of the full set after synchronization. This should ensure that the sets are identical in the end!
</dd>
</dl>
</section>
@@ -1855,8 +1857,8 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
+-----+-----+-----+-----+-----+-----+-----+-----+
| MSG SIZE | MSG TYPE | SEC | SETSIZE
+-----+-----+-----+-----+-----+-----+-----+-----+
- SETSIZE | SE-SLICES
- +-----+-----+-----+-----+
+ SETSIZE | SE-SLICES
+ +-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
]]></artwork>
@@ -1873,7 +1875,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
</dd>
<dt>SEC</dt>
<dd>
- is a 8-bit unsigned integer in networkf byte order, which indicates how many strata estimators
+ is a 8-bit unsigned integer in network byte order, which indicates how many strata estimators
with different salts are attached to the message. Valid values are 1,2,4 or 8, more details can be found
in the section <xref target="performance_multi_se" format="title" />.
</dd>
@@ -1902,13 +1904,13 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
SE-SLICE
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
- | SE_1->IBF_1 |
+ | SE_1 -> IBF_1
+-----+-----+-----+-----+-----+-----+-----+-----+
... ...
+-----+-----+-----+-----+-----+-----+-----+-----+
- | SE_1->IBF_30 |
+ | SE_1 -> IBF_30
+-----+-----+-----+-----+-----+-----+-----+-----+
- | SE_2->IBF_1 |
+ | SE_2 -> IBF_1
+-----+-----+-----+-----+-----+-----+-----+-----+
... ...
/ /
@@ -1973,8 +1975,8 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
+-----+-----+-----+-----+-----+-----+-----+-----+
| MSG SIZE | MSG TYPE | E TYPE | PADDING |
+-----+-----+-----+-----+-----+-----+-----+-----+
- | SIZE | AE TYPE | DATA
- +-----+-----+-----+-----+
+ | SIZE | AE TYPE | DATA
+ +-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
]]></artwork>
@@ -2253,22 +2255,23 @@ FUNCTION ibf_get_max_counter(ibf)
max_counter = bucket.counter
END IF
END FOR
- # next bigger discrete number of the binary logarithm of the max counter
+ # next bigger discrete number of the binary logarithm of the
+ # max counter
RETURN CEILING( LOG2( max_counter ) )
END FUNCTION
# INPUTS:
# ibf: The IBF
-# offset: The offset which defines the starting point from which bucket the
-# pack operation starts
+# offset: The offset which defines the starting point from which bucket
+# the pack operation starts
# count: The number of buckets in the array that will be packed
# OUTPUTS:
# returns: A byte array of packed counters to send over the network
# INPUTS:
# ibf: The IBF
-# offset: The offset which defines the starting point from which bucket the
-# pack operation starts
+# offset: The offset which defines the starting point from which bucket
+# the pack operation starts
# count: The number of buckets in the array that will be packed
# OUTPUTS:
# returns: A byte array of packed counters to send over the network
@@ -2278,7 +2281,7 @@ FUNCTION pack_counter(ibf, offset, count)
store_bits = 0
store = 0
byte_ctr = 0
- buffer=[]
+ buf=[]
FOR bucket IN ibf[offset] TO ibf[count] DO
counter = bucket.counter
@@ -2292,7 +2295,7 @@ FUNCTION pack_counter(ibf, offset, count)
bit_to_shift = byte_len - bit_free
store = store << bit_free
END IF
- buffer[byte_ctr] = (( counter >> bit_to_shift) | store) & 0xFF
+ buf[byte_ctr] = (( counter >> bit_to_shift) | store) & 0xFF
byte_ctr = byte_ctr + 1
byte_len -= 8 - store_bits
counter = counter & ((1 << byte_len) - 1)
@@ -2306,11 +2309,11 @@ FUNCTION pack_counter(ibf, offset, count)
# Write the last partial packed byte to the buffer
IF store_bits > 0 THEN
- buffer[byte_ctr] = store << (8 - store_bits)
+ buf[byte_ctr] = store << (8 - store_bits)
byte_ctr = byte_ctr + 1
END IF
- RETURN buffer
+ RETURN buf
FUNCTION END
# INPUTS:
@@ -2332,7 +2335,7 @@ FUNCTION unpack_counter(ibf, offset, count, cbl, pd)
byte_ctr = 0
WHILE TRUE
- byte_to_read = pd[byte_ctr]
+ byte_read = pd[byte_ctr]
bit_to_pack_left = 8
byte_ctr++
@@ -2350,10 +2353,10 @@ FUNCTION unpack_counter(ibf, offset, count, cbl, pd)
store = store << bit_use
END IF
bytes_to_shift = bit_to_pack_left - bit_use
- counter_partial = byte_to_read >> bytes_to_shift
+ counter_partial = byte_read >> bytes_to_shift
store = store | counter_partial
ibf.counter[ibf_bucket_ctr + offset] = store
- byte_to_read = byte_to_read & (( 1 << bytes_to_shift ) - 1)
+ byte_read = byte_read & (( 1 << bytes_to_shift ) - 1)
bit_to_pack_left -= bit_use
ibf_bucket_ctr++
@@ -2363,10 +2366,10 @@ FUNCTION unpack_counter(ibf, offset, count, cbl, pd)
store_bits = store_bits + bit_to_pack_left
IF 0 == store_bits THEN
- store = byte_to_read
+ store = byte_read
ELSE
store = store << bit_to_pack_left
- store = store | byte_to_read
+ store = store | byte_read
END IF
BREAK
END IF
@@ -2408,7 +2411,8 @@ END FUNCTION
# Inputs:
# value: Input value to salt (needs to be 64 bit unsigned)
-# salt: Salt to salt value with; Should always be ascending and start at zero
+# salt: Salt to salt value with; Should always be ascending and start
+# at zero
i.e. SE1 = Salt 0; SE2 = Salt 1 etc.
# Output:
# Returns: Salted value
@@ -2531,15 +2535,20 @@ END FUNCTION
<artwork name="" type="" align="left" alt=""><![CDATA[
-Chain for elements +---------+ +---------+ +---------+ +---------+
-NOT in IBF decoding | INQUIRY | ---> | OFFER | ===> | DEMAND | ===> | ELEMENT |
-peers set +---------+ +---------+ +---------+ +---------+
+Chain for
+elements +---------+ +---------+ +---------+ +---------+
+NOT in IBF | INQUIRY |--->| OFFER |===>| DEMAND |===>| ELEMENT |
+decoding +---------+ +---------+ +---------+ +---------+
+peers set
-Chain for elements +---------+ +---------+ +---------+
-in IBF decoding | OFFER | ---> | DEMAND | ===> | ELEMENT |
-peers set +---------+ +---------+ +---------+
- --->: Answer not mandatory
- ===>: Always answer needed.
+Chain for
+elements +---------+ +---------+ +---------+
+in IBF | OFFER |--->| DEMAND |===>| ELEMENT |
+decoding +---------+ +---------+ +---------+
+peers set
+
+ --->: Answer not mandatory
+ ===>: Always answer needed.
]]></artwork>
</figure>
<t>
@@ -3029,33 +3038,44 @@ END FUNCTION
<figure anchor="figure_constants">
<artwork name="" type="" align="left" alt=""><![CDATA[
Name | Value | Description
-----------------------------+------------+--------------------------
-SE_STRATA_COUNT | 32 | Number of IBFs in a strata estimator
-IBF_HASH_NUM* | 3 | Number of times an element is hashed to an
- IBF (from section 4.5.2)
-IBF_FACTOR* | 2 | The factor by which the size of the IBF is
- increased in case of decoding failure or
- initially from the set difference.
+----------------------------+------------+-------------------------------
+SE_STRATA_COUNT | 32 | Number of IBFs in a strata
+ estimator.
+IBF_HASH_NUM* | 3 | Number of times an element is
+ hashed to an IBF.
+ (from section 4.5.2)
+IBF_FACTOR* | 2 | The factor by which the size
+ of the IBF is increased in
+ case of decoding failure or
+ initially from the set
+ difference.
(from section 4.5.2)
-MAX_BUCKETS_PER_MESSAGE | 1120 | Maximum bucket of an IBF that are
- transmitted in single message
-IBF_MIN_SIZE* | 37 | Minimal number of buckets in an IBF
- (from section 3.8)
-DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed for a
+MAX_BUCKETS_PER_MESSAGE | 1120 | Maximum bucket of an IBF
+ that are transmitted in
+ single message.
+IBF_MIN_SIZE* | 37 | Minimal number of buckets
+ in an IBF. (from section 3.8)
+DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is
+ needed for a differential
+ synchronisation.
+SECURITY_LEVEL* | 2^80 | Security level for
+ probabilistic security
+ algorithms. (from section 5.8)
+PROBABILITY_FOR_NEW_ROUND* | 0.15 | The probability for a IBF
+ decoding failure in the
differential synchronisation
-SECURITY_LEVEL* | 2^80 | Security level for probabilistic security
- algorithms (from section 5.8)
-PROBABILITY_FOR_NEW_ROUND* | 0.15 | The probability for a IBF decoding failure
- in the differential synchronisation mode
- (from section 5.4)
-DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed for a
- differential synchronisation.
+ mode. (from section 5.4)
+DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed
+ for a differential
+ synchronisation.
(from section 4.5.3)
-MAX_IBF_SIZE | 1048576 | Maximal number of buckets in an IBF
-AVG_BYTE_SIZE_SE* | 4221 | Average byte size of a single strata
- estimator (from section 3.4.3)
-VALID_NUMBER_SE* | [1,2,4,8] | Valid number of SE in (from section 3.4)
-
+MAX_IBF_SIZE | 1048576 | Maximal number of buckets in
+ an IBF.
+AVG_BYTE_SIZE_SE* | 4221 | Average byte size of a single
+ strata estimator.
+ (from section 3.4.3)
+VALID_NUMBER_SE* | [1,2,4,8] | Valid number of SE's
+ (from section 3.4)
]]></artwork>
</figure>
@@ -3069,29 +3089,43 @@ VALID_NUMBER_SE* | [1,2,4,8] | Valid number of SE in (from section 3
<figure anchor="figure_purposenums">
<artwork name="" type="" align="left" alt=""><![CDATA[
Type | Name | References | Description
---------+----------------------------+------------+-----------------------------------
- 559 | SETU_P2P_REQUEST_FULL | [This.I-D] | Request the full set of the other
- peer
- 710 | SETU_P2P_SEND_FULL | [This.I-D] | Signals to send the full set to the
- other peer
- 560 | SETU_P2P_DEMAND | [This.I-D] | Demand the whole element from the
- other peer, given only the hash
- code.
- 561 | SETU_P2P_INQUIRY | [This.I-D] | Tell the other peer to send a list
- of hashes that match an IBF key.
- 562 | SETU_P2P_OFFER | [This.I-D] | Tell the other peer which hashes
- match a given IBF key.
- 563 | SETU_P2P_OPERATION_REQUEST | [This.I-D] | Request a set union operation from
- a remote peer.
- 564 | SETU_P2P_SE | [This.I-D] | Strata Estimator uncompressed
- 565 | SETU_P2P_IBF | [This.I-D] | Invertible Bloom Filter slices.
+--------+----------------------------+------------+----------------------
+ 559 | SETU_P2P_REQUEST_FULL | [This.I-D] | Request the full set
+ of the other peer.
+ 710 | SETU_P2P_SEND_FULL | [This.I-D] | Signals to send the
+ full set to the other
+ peer.
+ 560 | SETU_P2P_DEMAND | [This.I-D] | Demand the whole
+ element from the other
+ peer, given only the
+ hash code.
+ 561 | SETU_P2P_INQUIRY | [This.I-D] | Tell the other peer
+ to send a list of
+ hashes that match
+ an IBF key.
+ 562 | SETU_P2P_OFFER | [This.I-D] | Tell the other peer
+ which hashes match
+ a given IBF key.
+ 563 | SETU_P2P_OPERATION_REQUEST | [This.I-D] | Request a set union
+ operation from a
+ remote peer.
+ 564 | SETU_P2P_SE | [This.I-D] | Strata Estimator
+ uncompressed.
+ 565 | SETU_P2P_IBF | [This.I-D] | Invertible Bloom
+ Filter slices.
566 | SETU_P2P_ELEMENTS | [This.I-D] | Actual set elements.
- 567 | SETU_P2P_IBF_LAST | [This.I-D] | Invertible Bloom Filter Last Slice.
- 568 | SETU_P2P_DONE | [This.I-D] | Set operation is done.
- 569 | SETU_P2P_SEC | [This.I-D] | Strata Estimator compressed
- 570 | SETU_P2P_FULL_DONE | [This.I-D] | All elements in full synchronisation
- mode have been sent is done.
- 571 | SETU_P2P_FULL_ELEMENT | [This.I-D] | Send an actual element in full
+ 567 | SETU_P2P_IBF_LAST | [This.I-D] | Invertible Bloom
+ Filter Last Slices.
+ 568 | SETU_P2P_DONE | [This.I-D] | Set operation is
+ done.
+ 569 | SETU_P2P_SEC | [This.I-D] | Strata Estimator
+ compressed.
+ 570 | SETU_P2P_FULL_DONE | [This.I-D] | All elements in
+ full synchronisation
+ mode have been sent
+ is done.
+ 571 | SETU_P2P_FULL_ELEMENT | [This.I-D] | Send an actual
+ element in full
synchronisation mode.
]]></artwork>
