commit fa2765cf3c007c38725a1093c4502e05b63002f9
parent a6efc4c296f43ac1df5eb86c441f3aa380389fc1
Author: Elias Summermatter <elias.summermatter@seccom.ch>
Date: Sun, 13 Jun 2021 18:02:37 +0200
Fixed some more and added commets
Diffstat:
1 file changed, 24 insertions(+), 20 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -6,6 +6,7 @@
<!ENTITY RFC2782 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.2782.xml">
<!ENTITY RFC3686 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.3686.xml">
<!ENTITY RFC5869 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.5869.xml">
+ <!ENTITY RFC3385 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.3385.xml">
]>
<?xml-stylesheet type='text/xsl' href='rfc2629.xslt' ?>
<?rfc strict="yes" ?>
@@ -429,7 +430,7 @@ FUNCTION id_calculation (element,ibf_salt):
<t>
The HASH of an element ID is computed by calculating the
CRC32 checksum of the 64-bit ID value,
- which returns a 32-bit value. <!-- FIXME: CRC32 needs a reference! -->
+ which returns a 32-bit value.CRC32 is well-known and described in <relref section="4.1" target="RFC3385" displayFormat="of">the RFC</relref>.
</t>
</section>
@@ -603,7 +604,7 @@ hashSum | 0x0000 | 0x4242 | 0x0000 | 0x4242 |
<t>
Buckets in an IBF with a counter of 1 or -1 are crucial for decoding an IBF, as
they MIGHT represent only a single element, with the IDSUM being the ID of that element.
- Following Eppstein (FIXME-CITE), we will call buckets that only represent a single
+ Following Eppstein <xref target="Eppstein" format="default" />, we will call buckets that only represent a single
element <em>pure buckets</em>.
Note that due to the possibility of multiple insertion and removal operations
affecting the same bucket, not all buckets with a counter of 1 or -1 are
@@ -1091,7 +1092,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
the offered element is missing in the active peers set,
the active peer sends a <em><xref target="messages_demand" format="title" /></em> message to the
passive peer. The demand needs to be added to a list of unsatisfied demands.
- In case the received offer is for an element that is already in the set of the peer, the offer MUST BE ignored. <!-- FIXME: what do we do if the offer does not match any demand we ever issued? Is that OK? Worth checking? -->
+ In case the received offer is for an element that is already in the set of the peer, the offer MUST BE ignored. <!-- FIXME: what do we do if the offer does not match any demand we ever issued? Is that OK? Worth checking? @Christian: Demand? Demands come after offers.... You mean inquiry? In this case no because its possible that we get offers without an inquiry first... -->
</dd>
<dt><em><xref target="messages_demand" format="title" /></em> message:</dt>
<dd>
@@ -1165,7 +1166,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
The first case is when one of the peers announces having an empty set. This is announced by setting
the SETSIZE field in the <em><xref target="messages_se" format="title" /></em> to 0.
<!-- FIXME: why not also do this if sending the elements is about as
- expensive as sending the SE? Should be a simple calculation. -->
+ expensive as sending the SE? Should be a simple calculation. @Christian this is a future improvement but work to be done (thesis: future work) should i add stuff that is not already implemented? -->
The second case is if the application requests full synchronisation explicitly.
This is useful for testing and MUST NOT be used in production.
</t>
@@ -1297,7 +1298,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<dd>
is a 32-bit unsigned integer which signals the offset of the following IBF slices in the original.
</dd>
- <dt>SALT</dt> <!-- FIXME: do we need a 32-bit field here? Maybe use only 16 bits, and then have some room for IMCS without destroying alignment? -->
+ <dt>SALT</dt> <!-- FIXME: do we need a 32-bit field here? Maybe use only 16 bits, and then have some room for IMCS without destroying alignment? @Christian in my mind we need 32-bit(4,294,967,296) because with 16 we could only transmit an offset of 65,536 that's much less than max ibf size of 1,048,576-->
<dd>
is a 32-bit unsigned integer that contains the IBF-salt which was used to create the
IBF.
@@ -1310,7 +1311,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
by an array of HASHSUMS. Last comes an array of unsigned COUNTERS (details of the COUNTERS encoding are described in section
<xref target="performance_counter_variable_size" format="default"/>). The length of the array is
defined by MIN( SIZE - OFFSET, MAX_BUCKETS_PER_MESSAGE). MAX_BUCKETS_PER_MESSAGE is defined as
- 32768 divided by the BUCKET_SIZE which is 13 bytes (104 bits). <!-- FIXME: 13 byte is no longer correct, given variable-size counters! Should probably be computed by properly considering the IMCS value! -->
+ 32768 divided by the BUCKET_SIZE which ranges between 97-bits when counter uses bit 1 (IMCS=1) and 160-bit when counter size uses 64 bit (IMCS=64).
</t>
<t>
To get the IDSUM field, all IDs (computed with the IBF-salt) hitting a bucket under the map M are added up with a binary XOR operation.
@@ -1409,8 +1410,8 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
+-----+-----+-----+-----+-----+-----+-----+-----+
| MSG SIZE | MSG TYPE | E TYPE | PADDING |
+-----+-----+-----+-----+-----+-----+-----+-----+
- | E SIZE | AE TYPE | DATA
- +-----+-----+-----+-----+ /
+ | E SIZE | DATA
+ +-----+-----+ /
/ /
/ /
]]></artwork>
@@ -1438,11 +1439,6 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<dd>
is a 16-bit unsigned integer that signals the size of the elements data part.
</dd>
- <dt>AE TYPE</dt><!-- FIXME: E TYPE vs. AE TYPE remains quite unclear to me. Why do we have both? If we get rid of one, we could also drop PADDING! -->
- <dd>
- is a 16-bit unsigned integer that is needed to identify
- the type of element that is in the data field.
- </dd>
<dt>DATA</dt>
<dd>
is a field with variable length that contains the data of the element.
@@ -1476,7 +1472,7 @@ 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 | HASHES
+-----+-----+-----+-----+
/ /
/ /
@@ -1492,10 +1488,10 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<dd>
is SETU_P2P_OFFER as registered in <xref target="gana" format="title" /> in network byte order.
</dd>
- <dt>HASH</dt>
+ <dt>HASHES</dt>
<dd>
- is a SHA 512-bit hash of the element that is requested with a <em><xref target="messages_inquiry" format="title" /></em> message.
- </dd><!-- FIXME: OFFER 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! -->
+ contains one or more successive SHA 512-bit hashes of the elements that are requested with <em><xref target="messages_inquiry" format="title" /></em> messages.
+ </dd>
</dl>
</section>
</section>
@@ -1523,8 +1519,16 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
+-----+-----+-----+-----+-----+-----+-----+-----+
| MSG SIZE | MSG TYPE | SALT |
+-----+-----+-----+-----+-----+-----+-----+-----+
- | IBF KEY |
+ | IBF KEY 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
+ | IBF KEY 2 |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ ... ...
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ | IBF KEY n |
+ +-----+-----+-----+-----+-----+-----+-----+-----+
+ / /
+ / /
]]></artwork>
</figure>
<t>where:</t>
@@ -1539,10 +1543,9 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
</dd>
<dt>IBF KEY</dt>
<dd>
- is a 64-bit unsigned integer that contains the key for which the inquiry is sent.
+ contains one or more successive ibf key (64-bit unsigned integer) for which the inquiry is sent.
</dd>
</dl>
- <!-- FIXME: INQUIRY was defined as a variable-size message that CAN include multiple IBF KEY values in one message. I did not check if the current code uses this, but we should continue to define it as such in the protocol - especially as for INQUIRIES this is particularly easy to implement and an important optimization given that the overhead is otherwise rather large per IBF KEY! -->
</section>
</section>
@@ -3107,6 +3110,7 @@ Type | Name | References | Description
<name>Normative References</name>
&RFC5869;
&RFC2119;
+ &RFC3385;
<reference anchor="byzantine_fault_tolerant_set_reconciliation" target="https://summermatter.net/byzantine-fault-tolerant-set-reconciliation-summermatter.pdf">
<front>
