commit 7f1907783383e568661ae6dbaa672806c32a243e
parent 7e26639340f951684c7593b400d8f4fb68a3977c
Author: Elias Summermatter <elias.summermatter@seccom.ch>
Date: Sun, 13 Jun 2021 21:45:17 +0200
Added some more stuff
Diffstat:
1 file changed, 41 insertions(+), 30 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -7,6 +7,7 @@
<!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">
+ <!ENTITY RFC1951 PUBLIC '' "http://xml.resource.org/public/rfc/bibxml/reference.RFC.1951.xml">
]>
<?xml-stylesheet type='text/xsl' href='rfc2629.xslt' ?>
<?rfc strict="yes" ?>
@@ -168,7 +169,7 @@
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL
NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described
- in<xref target="RFC2119"/>.
+ in <xref target="RFC2119"/>.
</t>
</section>
@@ -1002,7 +1003,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
that are missing from the active peer's set.
In this case the passive peer answers with <em><xref target="messages_offer" format="title" /></em> messages
which contain the SHA-512 hash of the requested element. If the passive peer does not have an element with
- a matching element ID, it MUST ignore the inquiry (in this case, a bucket was falsely classified as pure, decoding the IBF will eventually fail, and roles will be swapped). <!-- FIXME: should we not remember that this happened and FAIL if the other peer sends DONE instead of an IBF? -->
+ a matching element ID, it MUST ignore the inquiry (in this case, a bucket was falsely classified as pure, decoding the IBF will eventually fail, and roles will be swapped). <!-- FIXME: should we not remember that this happened and FAIL if the other peer sends DONE instead of an IBF? @Christian this is not implemented should I add it to the RFC anyways? -->
If multiple elements match the 64 bit element ID, the passive
peer MUST send offers for all of the matching elements.
</dd>
@@ -1827,7 +1828,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
More details can be found in section <xref target="performance_multi_se" format="title" />.
</t>
<t>
- The IBFs in a strata estimator always have 79 buckets. The reason why can be found in Summermatter's work. <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>
+ The IBFs in a strata estimator always have 79 buckets. The reason why can be found in Summermatter's work in section 3.4.2. <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>
</t>
<!-- Give a more precise reference into the thesis for this, do not cite the whole thesis! -->
</section>
@@ -1865,7 +1866,7 @@ 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 -->
+ <!-- CORRECT START -->
<dt>SE-SLICES</dt>
<dd>
<t>
@@ -1882,6 +1883,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
</t>
</dd>
</dl>
+ <!-- CORRECT END -->
<figure anchor="figure_se_slice">
<artwork name="" type="" align="left" alt=""><![CDATA[
SE-SLICE
@@ -1908,15 +1910,18 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<section anchor="messages_sec_description" numbered="true" toc="default">
<name>Description</name>
+ <!-- CORRECT START -->
<t>
- The Strata estimator can be compressed with gzip to improve performance. This can be recognized
+ The Strata estimator can be compressed (the SE-Slices are compressed the header stays uncompressed) with gzip as
+ described in <xref target="RFC1951"/> to improve performance. This can be recognized
by the different message type number from <xref target="gana" format="title" />.
</t>
+ <!-- CORRECT END -->
<t>
Since the content of the message is the same as the uncompressed Strata Estimator, the details
are not repeated here. For details see section <xref target="messages_se" format="counter" />.
</t>
- <!-- FIXME: keep the 'structure' subsection, and also needs to clarify WHAT is being
+ <!-- FIXME: keep the 'structure' subsection , and also needs to clarify WHAT is being @Christian but then the Structure section is just a copy of the one above? Isn't this pointless?
compressed, and should cite the RFC on the compression method used! (IIRC gzip deflate
mode); note that the header is not subject to compression, so this must be clarified!) -->
</section>
@@ -2003,7 +2008,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<name>Operation Mode</name>
<t>
The decision which <xref target="modeofoperation" format="title"/> is used is described by the following code.
- More detailed explanations motivating the design can be found in the accompanying thesis.<xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>
+ More detailed explanations motivating the design can be found in the accompanying thesis in section 4.5.3.<xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>
</t>
<t>
The function takes as input the average element size, the local set size, the remote set size, the set differences as estimated from the strata estimator for both the local and remote sets,
@@ -2014,15 +2019,15 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
DIFFERENTIAL_SYNC if the differential synchronisation is optimal.
</t>
<t>
- The constant IBF_BUCKET_NUMBER_FACTOR is always 3 and IBF_MIN_SIZE is 37.
- <!-- Above we wrote 79. What gives? Also, didn't your thesis somewhere conclude
- that the IBF FACTOR should be 2? You also write 2 in the function below!
+ The constant IBF_BUCKET_NUMBER_FACTOR is always 2 and IBF_MIN_SIZE is 37.
+ <!-- Above we wrote 79. What gives? @Christian79 is the static size for the SEs and 37 is the minimal size for an IBF//. Also, didn't your thesis somewhere conclude
+ that the IBF FACTOR should be 2? @Christian Your right :-)) You also write 2 in the function below!
Please cite exact parts of the thesis, not the entire document! -->
The method for deriving
- this can be found in Summermatter's work. <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>
+ this can be found in the IBF parameter study in Summermatter's work in section 4.5.2. <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>
</t>
<figure anchor="performance_formulas_operationmode_code">
- <!-- Why use RTT_MIN_FULL=2, if the average is 2.25? -->
+ <!-- Why use RTT_MIN_FULL=2, if the average is 2.25? @Christian this are just the minimum (RTT_MIN_FULL) round tips not an avg. -->
<artwork name="" type="" align="left" alt=""><![CDATA[
# CONSTANTS:
# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if decoding fails
@@ -2122,7 +2127,7 @@ FUNCTION decide_operation_mode(avg_es,
RETURN DIFFERENTIAL_SYNC
IF END
]]></artwork>
-<!-- FIXME: the above algorithm is a mess, starting with formatting;
+<!-- FIXME: the above algorithm is a mess, starting with formatting; @Better now?
please begin by using shorter variable names and formatting so
that it renders properly in the HTML. Then, add some comments.
Also note that I switched the first two conditions, which
@@ -2137,8 +2142,8 @@ FUNCTION decide_operation_mode(avg_es,
</t>
<t>
These algorithms are described and justified in more details in
- <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>.
- <!-- FIXME: cite more precisely where in the thesis! -->
+ <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/> in the parameter study in
+ section 3.5.2, the max IBF counter in section 3.10 and the Improved IBF size in section 3.11.
</t>
<figure anchor="performance_formula_ibf_parameters_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
@@ -2173,9 +2178,8 @@ FUNCTION END
<t>
The number of buckets an element is hashed to is hardcoded to 3. Reasoning and
justification can be found in the following work
- <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>.
- <!-- FIXME: Maybe this is better simply left to section 9 constants?
- Again, be precise in which part of your thesis you cite. -->
+ <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/> in the
+ IBF parameter performance study in section 4.5.2.
</t>
</section>
</section>
@@ -2184,7 +2188,8 @@ FUNCTION END
<t>
Since the optimal number of bytes a counter in the IBF contains is very variable and varies
due to different parameters. Details are described in the BSC thesis
- by Summermatter <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>.
+ by Summermatter <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>
+ in section 3.2.
Therefore a packing algorithm has been implemented, which always creates the IBF counter in optimal size.
and thus minimizes the bandwidth needed to transmit the IBF.
</t>
@@ -2375,7 +2380,8 @@ FUNCTION se_key_salting(value, salt)
]]></artwork>
</figure>
<t>
- Performance study and details about the reasoning for the used methods can be found in the work of Summermatter.
+ Performance study and details about the reasoning for the used methods can be found in the work of Summermatter in section
+ 3.4.1 under the title "Added Support for Multiple Strata Estimators".
<xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>
</t>
</section>
@@ -2679,7 +2685,7 @@ FUNCTION END
]]></artwork>
</figure>
<t>
- This is based on the work of Summermatter. More details can be found in his thesis <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>.
+ This is based on the work of Summermatter. More details can be found in his thesis <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/> in section 5.3 (Message Control Flow).
</t>
</section>
@@ -2693,7 +2699,7 @@ FUNCTION END
<t>
The question after how many active/passive switches it can be assumed that the other peer is not honest,
depends on many factors and can only be solved probabilistically. In the work of Summermatter <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>
- this is described in detail. From this work it is concluded that the probability of decoding failure is about
+ in the section 5.4 this is described in detail. From this work it is concluded that the probability of decoding failure is about
15% for each round. The probability that there will be n active/passive changes is given by 0.15^{round number}.
Which means that after about 30 active/passive switches it can be said with a certainty of 2^80 that one of the peers
is not following the protocol. It is reasonable that a maximum of 30 active/passive changes should be set.
@@ -2712,7 +2718,7 @@ FUNCTION END
of operation.
</t>
<t>
- In order to calculate this plausibility, in Summmermatters paper <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>
+ In order to calculate this plausibility, in Summmermatters paper <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/> in section 5.5
a formula was developed, which depicts the probability with which one
can calculate the corresponding plausibility based on the number of
new and repeated elements after each received element.
@@ -3069,7 +3075,7 @@ FUNCTION END
<name>Constants</name>
<t>
The following table contains constants used by the protocol. The constants marked with a * are
- validated through experiments in Summermatter's work <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>.
+ validated through experiments in Summermatter's work <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/> in sections given below.
</t>
<figure anchor="figure_constants">
<artwork name="" type="" align="left" alt=""><![CDATA[
@@ -3077,25 +3083,29 @@ 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
+ 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
+ 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
differential synchronisation
SECURITY_LEVEL* | 2^80 | Security level for probabilistic security
- algorithms
+ 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
+ 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
-VALID_NUMBER_SE* | [1,2,4,8] | Valid number of SE in
+ estimator (from section 3.4.3)
+VALID_NUMBER_SE* | [1,2,4,8] | Valid number of SE in (from section 3.4)
]]></artwork>
</figure>
@@ -3153,6 +3163,7 @@ Type | Name | References | Description
&RFC5869;
&RFC2119;
&RFC3385;
+ &RFC1951;
<reference anchor="byzantine_fault_tolerant_set_reconciliation" target="https://summermatter.net/byzantine-fault-tolerant-set-reconciliation-summermatter.pdf">
<front>
